A number is called n-factor if it has exactly n distinct prime factors. Given positive integers a, b, and n, you have to find the number of integers between a and b, inclusive, that are n-factor. We consider 1 to be 0-factor.

Input Format:
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 a, b, and n as described above.

Output Format:
Output for each test case one line containing the number of n-factor integers in [a, b].

Constraints:
T < 10000
1 ≤ a ≤ b ≤ 10^6
0 ≤ n ≤ 10