Link to Russian translation of problem

Monk has been solving a lot of mathematical problems recently. He was learning ETF (Euler Totient Function) and found the topic quite interesting. So, he tried solving a question on ETF. He will be given two numbers L and R. He has to find the probability that the ETF of a number in the range [L, R] is divisible by a number K.
Note:
ETF is an arithmetic function that counts the positive integers less than or equal to N that are relatively prime to N. To learn more about ETF, click here.

Input:
The first line contains the number of test cases i.e. T.
The next T lines will contain three integers L, R and K.

Output:
Print the answer in a new line after rounding off the first 6 digits after the decimal place.

Constraints:
1 <= T <= 10
1 <= L <= R <= 10¹²
0 <= R - L <= 10⁵
1 <= K <= 10⁶