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 >
	Mitch Schwartz: 2015-01-15 13:57:43 1. The problem looks interesting. :) 2. It could be good to put a warning that source limit is lower than usual, so people know before they start coding. 3. Were slower languages considered when designing test data size + time limit?