NFACTOR  NFactorful
A number is called nfactorful 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 nfactorful. We consider 1 to be 0factorful.
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 ≤ 10^{6}
0 ≤ n ≤ 10
Output
Output for each test case one line containing the number of nfactorful integers in [a, b].
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
papan_97:
20201016 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:
20200627 09:50:52
NT:Be careful...


zhalok:
20200523 09:35:38
how to do this using upper bound and lower bound


sahajjaiswal:
20200515 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:
20200328 10:25:37
sd 

enigma_112:
20200303 23:04:09
AC in one attempt :) 

tanav_shah1:
20191105 21:13:39
Excellent question!!! Great use of sieve.


aayush_b1999:
20190718 19:30:49
@rajat813 these are the 6 integers


rajat813:
20190314 00:45:51
how answer of


ameyanator:
20180322 23:05:44
I've got a O(T+(X*root(X)) approach where X=10^6. Used preprocessing memoization. I've got an AC @1.18 secs but I see people with quite less runtimes ~<0.5secs. Whats the approach for it? 
Added by:  periclesmachado 
Date:  20110130 
Time limit:  1.879s2.484s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Facebook Hacker Cup 2011 Round 1C 