N-Factorful

https://www.facebook.com/codingcompetitions/hacker-cup/2011/round-1c/problems/A

Question

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

Input Format

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

Constraints

$$T = 20$$

$$1 ≤ a ≤ b ≤ 10^7$$

$$0 ≤ n ≤ 10$$

Output Format

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

Sample Inputs:

Input 0

Input

5
1 3 1
1 10 2
1 10 3
1 100 3
1 1000 0

Output

2
2
0
8
1

---

Solution