I. Interesting Pairs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three integers $$$l$$$, $$$r$$$ and $$$k$$$. Find the number of pairs $$$(a, b)$$$ such that $$$l$$$ $$$\leq$$$ $$$a$$$ $$$\leq$$$ $$$b$$$ $$$\leq$$$ $$$r$$$ and $$$\frac{LCM (a, b) }{GCD (a, b)}$$$ $$$=$$$ $$$k$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1$$$ $$$\leq$$$ $$$t$$$ $$$\leq$$$ $$$100)$$$.

The first (and only) line of each test case contains three integers $$$l$$$, $$$r$$$ and $$$k$$$ $$$(1$$$ $$$\leq$$$ $$$l$$$ $$$\leq$$$ $$$r$$$ $$$\leq$$$ $$$10^9$$$, $$$1$$$ $$$\leq$$$ $$$k$$$ $$$\leq$$$ $$$10^9)$$$.

Output

For each test case, print a single integer — the number of pairs.

Example
Input
5
1 20 5
5 15 6
20 23 3
11 2022 18
11 111 1
Output
4
3
0
321
101
Note

In the second test case, the pairs are (6, 9), (8, 12), (10, 15).