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.

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
amatuer_42: 2019-04-05 05:58:25

Last edit: 2019-04-05 06:26:19
van_persie9: 2018-05-24 23:08:11

@Lakshman can you please tell where I need to optimize my code?
I am getting TLE

==(Lakshman)==>Your query part is taking time and in the worst case it is O(n).

Last edit: 2018-06-08 08:33:44
jha4032: 2018-03-22 03:15:31

just precalculate ...... and ............. AC(0.08 sec)

Last edit: 2018-03-22 03:16:08
satyampnc: 2017-10-12 09:34:55

huh..finally AC in 0.18sec after 4 WA.....!!!

Last edit: 2017-10-12 09:35:54
jayharsh: 2017-08-18 09:25:48

Too many times TLE but after get the AC......precomputation is the best

jayharsh: 2017-08-15 21:48:26

@Lakshman please check my approach.....it is giving TLE

==Lakshman==> In worst for each query it is taking $O(n)$. Here you need $O(log n) $for each query.

Last edit: 2018-01-26 14:03:35
congru_mod: 2017-07-03 12:11:55

finally AC after so many WA!!!!!

vivace: 2016-12-11 08:41:32

precomputation at its best :)

sandy: 2016-11-21 10:37:41

@Lakshman- hey, I'm getting tled, my query is log n and i've precomputed the depth. Can you please tell me where i'm going wrong.
Thank you

karan_batra: 2016-09-13 11:12:11

Nice one


Added by:[Lakshman]
Date:2015-01-14
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:ETF