All submissions for this problem are available.
Bob has given Scoop and Muck their new task. As of now, they are at House number X and Y. They have to fix some houses hi (X<=hi<=Y) in a straight lane.
Things can be strange in their world. Only those houses have a problem and need to be fixed whose number is a N-Prime-divisors.
A number is N-Prime-divisors if it has exactly N distinct prime divisors.
For example number 4 is 1-Prime-divisors-number, number 42 is 3-Prime-divisors-number.
So Scoop and Muck start from their places and move towards each other fixing all houses that are N-Prime-divisors. By time they meet, how many houses they have fixed in total(inclusive of the house where they meet)?
Note : A prime number is 1-Prime-Divisor because it is divisible by itself.
- The first line of the input contains an integer T denoting the number of test cases.
Each test case contains three numbers X,Y and N separated by a space.
For each testcase, output on a separate line the number of N-Prime-divisors between X & Y.
- 1 ≤ T ≤ 104
- 2 ≤ X ≤ Y <= 105
- 1 ≤ N ≤ 10
Input: 4 2 4 1 4 10 1 6 12 2 Output: 3 5 3
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions