monk-and-etf

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^12
0 ≤ R - L ≤ 10^5
1 ≤ K ≤ 10^6

SAMPLE INPUT
3
1 4 2
2 5 2
3 10 4

SAMPLE OUTPUT
0.500000
0.750000
0.375000

Explanation

In Case 1:
ETF values of numbers from 1 to 4 are - 1, 1, 2, 2. Probability that ETF value is divisible by 2 is (2/4) = 0.5
In Case 2:
ETF values of numbers from 2 to 5 are - 1, 2, 2, 4. Probability that ETF value is divisible by 2 is (3/4) = 0.75
In Case 3:
ETF values of numbers from 3 to 10 are - 2, 2, 4, 2, 6, 4, 6, 4. Probability that ETF value is divisible by 4 is (3/8) = 0.375

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics


Solutions: