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
besteady:
20160906 15:11:35
@Lakshman  Hey, can you please check why I am getting WA ?


square1001:
20160730 03:16:08
@Lakshman  This problem is good, but I think this problem is so similar to ProjectEuler 214. Last edit: 20160730 03:16:55 

Ashutosh:
20160708 23:41:38
Last edit: 20160709 00:04:50 

somya_v:
20160326 14:36:27
@Lakshman can you please tell that which part in my code needs optimization...?


[Lakshman]:
20151128 02:51:29
@MuKeSh$ try to submit your own code don't cheat. I have disqualified your submission. 

:.Mohib.::
20151022 23:31:06
Finally did It....!! Thanx @Lakshman for the great problem... :) 

:.Mohib.::
20150716 16:55:04
@Lakshman can you please tell in my last submission, in which part I should optimize or in which part I am doing repeated calculations?? Thanks...


:.Mohib.::
20150716 14:45:03
@Lakshman can you please check my code...I should optimize more or there is a specific algorithm to solve this que??


deathgun:
20150602 15:10:39
Nice Ques.. my 150th :D 
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 