Background

卑鄙的konami将01的伙伴簧绑走了，如今01将要去救她。

Description

要想救出簧，01需要破译密码，需要回答很多类似的问题：

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

作为01的同伴，01希望得到你的帮助。

Input

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

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

Output

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

Samples

2
4 5 2
6 4 3

3
2

样例解释

第一组数据 4 5 2 共有三组满足题目要求分别是2 2,2 4,4 2

第二组数据 6 4 3 共有两组满足题目要求分别是3 3,6 3

Limitation

1s, 1024KiB for each test case.

1≤n≤10000, 1≤d≤a,b≤5000

gcd(x,y) 返回 x，y的最大公约数。