## NFACTOR - N-Factorful

A number is called n-factorful if it has exactly n distinct prime factors. Given positive integers ab, 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 ab, 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 [ab].

### Example

```Input:
5
1 3 1
1 10 2
1 10 3
1 100 3
1 1000 0

Output:
2
2
0
8
1```

hide comments
 < Previous 1 2 3 4 5 6 7 Next > divyansh96: 2024-04-03 12:27:12 Nice Question, Got it After some optimization :) joe201610a: 2022-04-06 21:49:02 BROOOO SO EASY AC IN ONE GO WITH FORMULA ONLY EZZZZZZZZZZZZ ramizouari: 2021-12-20 21:56:09 It can be solved using a Segment Tree, or even an Ordered Statistic Tree erne1309: 2021-07-22 03:55:29 got ac with sieve+prefix[10][1e6] conganon: 2021-07-05 04:12:26 :V papan_97: 2020-10-16 16:19:33 How are people using upper/lower bound and why? I got ac in 0.40 seconds with simple sieve+prefix sum in cpp O_o fetus: 2020-06-27 09:50:52 NT:Be careful... 1. when n=0 and a=1 2.when n=0 but a>1 and use 2D vector and upper_bound and lower_bound Last edit: 2020-06-27 09:56:21 zhalok: 2020-05-23 09:35:38 how to do this using upper bound and lower bound sahajjaiswal: 2020-05-15 13:58:54 The only thing I hate about spot discussions is "AC in one go". I really don't know why it's required here. I think that discussion platform is meant for doubts and clarification. amanjaiswal123: 2020-03-28 10:25:37 sd

 Added by: periclesmachado Date: 2011-01-30 Time limit: 1.879s-2.484s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: Facebook Hacker Cup 2011 Round 1C