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₀ = x, and for n > 0: a_n = phi(a_n-1), 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⁶
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

< Previous 1 2 3 4 Next >
	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
	besteady: 2016-09-06 15:11:35 @Lakshman - Hey, can you please check why I am getting WA ?
	square1001: 2016-07-30 03:16:08 @Lakshman - This problem is good, but I think this problem is so similar to ProjectEuler 214. Last edit: 2016-07-30 03:16:55
	somya_v: 2016-03-26 14:36:27 @Lakshman can you please tell that which part in my code needs optimization...? I am getting TLE ==(Lakshman)==> You are getting TLE on query part, Query part should be done in logarithmic time not in liner. Last edit: 2016-05-03 08:57:35
	[Lakshman]: 2015-11-28 02:51:29 @MuKeSh$ try to submit your own code don't cheat. I have disqualified your submission.
	:.Mohib.:: 2015-10-22 23:31:06 Finally did It....!! Thanx @Lakshman for the great problem... :)
	:.Mohib.:: 2015-07-16 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... =(Lakshman)=>ETF part is okay. You need to answer each Query in Logarithmic time. Last edit: 2015-07-17 05:17:07
	:.Mohib.:: 2015-07-16 14:45:03 @Lakshman can you please check my code...I should optimize more or there is a specific algorithm to solve this que?? =(Lakshman)=> I just looked at your code, 1. You are computing same thing again and again. 2. You have to answer each Query in O(log n) time with some Pre-computation if Required. You have TLE in both Small and Large input files. Last edit: 2015-07-16 14:56:55
	deathgun: 2015-06-02 15:10:39 Nice Ques.. my 150th :D