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
erne1309:
20210722 03:55:29
got ac with sieve+prefix[10][1e6] 

conganon:
20210705 04:12:26
:V


dgenxsid:
20210501 10:08:19
I'm a lamer. Last edit: 20210501 12:39:33 

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.

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 