3

NFACTOR

Difficulty: HARD
Avg. time to solve
50 min
Success Rate
50%

Problem Statement
Suggest Edit

You have given ‘Q’ queries where each query is represented by three positive integers ‘A’, ‘B’ and ‘N’. For each query, you are supposed to find the number of integers in the range [A, B] which has exactly ‘N’ unique prime factors.

Input Format :

The first line contains an integer ‘Q’ denoting the number of queries.

The next ‘Q’ lines contain three space-separated integers ‘A’, ‘B’ and ‘N’ which are described in the problem statement. 

Output Format :

For each query, print the number of integers in the range [A, B] which has exactly ‘N’ unique prime factors. 


The output of each query will be printed in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints :

1 <= Q <= 10000
1 <= A, B <= 10000
1 <= N <= 10

Where ‘Q’ is the number of queries and ‘A’, 'B’ and ‘N’ are three integers as described in the problem statement.

Time limit: 1 sec

Sample Input 1 :

2
3 8 2
1 8 1

Sample output 1 :

1
6

Explanation of Sample output 1 :

For the first test case, 6 is the only integer in the range [3, 8] which has exactly 2 unique prime factors, 2 and 3.

For the second test case, [2, 3, 4, 5, 7, 8] will have exactly 1 unique prime factor.

Sample Input 2 :

2
1 10 3
1 2 1

Sample output 2 :

0
1

Explanation of Sample output 2 :

For the first test case, there is no number in the range [1, 10] which has 3 unique prime factors.

For the second test case, 2 has 1 unique prime factor.
Reset Code
Full screen
copy-code
Console