Rohil and Mahesh recently attended a class on Prime Numbers. They learnt about a term "Prime Score" which is defined for all N > 1. For a number N = p₁^a × p₂^b × p₃^b × ... × p_k^m where p₁, p₂ ... p_k are prime factors of N, Prime Score of N = a + b + ... + m.

While Mahesh was interested only in primes, Rohil thought how about playing around with composite numbers. Both started discussing and found out something known as Perfect Composite Numbers. They defined a composite number N as Perfect Composite if it is divisible by all the divisors of its Prime Score.

Whoa!! That's a nice discovery both of them have made. Now, they are interested in finding the number of Perfect Composites between A and B (inclusive) having Prime Score K. They want you to write a program for the same.

Input

First line contains a single integer T ≤ 10000, the number of test cases. Each following line contains three integers A, B and K (2 ≤ A ≤ B ≤ 10⁵ and K ≥ 0).

Output

For each test case, print a single integer - the number of Perfect Composite numbers between A and B (inclusive) having Prime Score = K.

Example

Input:
5
2 5 2
3 100 3
4 10 5
90 456 8
34 67 5

Output:
1
11
0
2
0