cyk: THE BIG HANDSOME GOD
One day, bLue met cyk and thought that cyk looked so handsome.
bLue wanted to be handsome like cyk, then he would be able to find a girl friend. So he asked cyk how can be handsome.
cyk said that there's an interesting problem and if bLue can solve it, he would teach him how to be handsome.
The problem is:
There's an exciting number k. You should calculate how many numbers in range [c, y] is (their GCD equals 1) with k.
For bLue's future, can you help him to solve the problem?
The first line of input contains one integer T (0 < T <= 100), denoting the number of test cases.
For each case, it contains 3 integer c, y, k (0 < c <= y <= 10^15, 0 < k < 10^9) separated by spaces in one line.
For each case, output an integer in one line, denoting the answer.
2 1 10 2 3 10 5