题目描述

达达正在破解一段密码，他需要回答很多类似的问题：

对于给定的整数 $\red a$ , $\red b$ 和 $\red d$，有多少正整数对 $\red x$ , $\red y$，满足 $\red{x<=a}$，$\red{y<=b}$，并且 $\red{gcd(x,y)=d}$。

作为达达的同学，达达希望得到你的帮助。

输入格式

第一行包含一个正整数 $\red n$，表示一共有 $\red n$ 组询问。

接下来 $\red n$ 行，每行表示一个询问，每行三个正整数，分别为 $\red a$ , $\red b$ , $\red d$。

输出格式

对于每组询问，输出一个正整数，表示满足条件的整数对数。

样例

输入样例

2
4 5 2
6 4 3

输出样例

3
2

提示

$\red{1\leq n\leq 50000}$,

$\red{1\leq d\leq a,b\leq 50000}$