3

# NFACTOR

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

Problem Statement
Suggest Edit

#### 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.
``````
Console