Co-prime#2725
Given a number , you are asked to count the number of integers between and , inclusive, which are relatively prime to .
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than , or, equivalently, if their greatest common divisor is . The number is relatively prime to every integer.
The first line contains (0 < T \leq 100), the number of test cases. Each of the next lines contains three integers , , and , where 1 \leq A \leq B \leq 10^{15} and 1 \leq N \leq 10^9.
For each test case, print the number of integers between and , inclusive, which are relatively prime to .
Example 1