spoj#NFACTOR. N-Factorful
N-Factorful
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
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.
T > 10000
1 ≤ a ≤ b ≤ 106
0 ≤ n ≤ 10
Output
Output for each test case one line containing the number of n-factorful integers in [a, b].
Example
Input: 5 1 3 1 1 10 2 1 10 3 1 100 3 1 1000 0</p>Output: 2 2 0 8 1