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 a_{0} = x, and for n > 0: a_{n} = phi(a_{n1}), this sequence will be constant equal to 1 starting from some point. Lets define depth(x) as minimal n such that a_{n} = 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.
Input
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
Output for each test case one line containing the count of all numbers whose depth equals to k in given range [m, n].
Constraints
T < 10001
1 ≤ m ≤ n ≤ 10^{6}
0 ≤ k < 20
Example
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.
hide comments
sankalp_7:
20210708 14:51:55
I precomputed in 2D array.


subhashis_cse:
20200718 17:32:24
AC in 1 go :D 

poojitha_792:
20200626 10:30:45
@lakshman can u pls look at my code i am getting tle 

van_persie9:
20180524 23:08:11
@Lakshman can you please tell where I need to optimize my code?


jha4032:
20180322 03:15:31
just precalculate ...... and ............. AC(0.08 sec) Last edit: 20180322 03:16:08 

satyampnc:
20171012 09:34:55
huh..finally AC in 0.18sec after 4 WA.....!!!


jayharsh:
20170818 09:25:48
Too many times TLE but after get the AC......precomputation is the best 

jayharsh:
20170815 21:48:26
@Lakshman please check my approach.....it is giving TLE


congru_mod:
20170703 12:11:55
finally AC after so many WA!!!!!


vivace:
20161211 08:41:32
precomputation at its best :) 
Added by:  [Lakshman] 
Date:  20150114 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  ETF 