cyk: THE BIG HANDSOME GOD

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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 coprime (their GCD equals 1) with k.


For bLue's future, can you help him to solve the problem?

Input

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.

Output

For each case, output an integer in one line, denoting the answer.

Sample Input

2
1 10 2
3 10 5

Sample Output

5
6

Hint

Source

【第八届山东理工大学ACM网络编程擂台赛 正式赛】Q^Q (cyk)