ETFD - Euler Totient Function Depth
Lucky is fond of Number theory,
one day he was solving a problem related to Euler Totient Function (phi) and
found an interesting property of phi :
phi(1) = 1, and for x > 1: phi(x) < x.
So if we define a sequence with a0 = x, and for n > 0: an = phi(an-1), this sequence will be constant equal to 1 starting from some point. Lets define depth(x) as minimal n such that an = 1.
Now he is wondering how many numbers in a given range have depth equal to given number k. As you are a good programmer help Lucky with his task.
Your input will consist of a single integer T followed by a newline and T test cases. Each test cases consists of a single line containing integers m, n, and k.
Output for each test case one line containing the count of all numbers whose depth equals to k in given range [m, n].
T < 10001 1 ≤ m ≤ n ≤ 10^6 0 ≤ k < 20
Input: 5 1 3 1 1 10 2 1 10 3 1 100 3 1 1000000 17 Output: 1 3 5 8 287876
Explanation ::suppose number is 5 ; its depth will be 3. ( 5 -> 4 -> 2 -> 1 )
Note ::Depth for 1 is 0.