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
minhthai:
20160205 13:25:15
such a nice problem! Be careful with your "limit" though :) 

dwij28:
20160106 06:57:55
Amazing ! If anyone ever asks me the list of best questions on SPOJ, this one is gonna rank very very high. Several TLE's before AC with 0.09 seconds. I applied memorization, 2D vectors, adapted sieve of eratosthenes, fast io, etc before finally realizing that my mistake was that i was iterating through all elements in (a, b) while using memorization. Used the std::upper_bound and std::lower_bound functions to finally get the green tick. 

Md.Mahmudul Hasan:
20151201 01:22:50
use 2d vector and push number in vector like vector[ factor] .push_back(number) and find upper bound and lower bound and res=upper_boundlower_bound. 

SangKuan:
20151027 10:38:37
Great problem 

newbie:
20151020 06:41:12
Got AC in 0.64.


robin_0:
20150824 10:05:54
Wonderful Problem =D


:.Mohib.::
20150627 22:08:14
Very Nice problem!! 

kp:
20150626 10:11:17
learnt a lot.. awesome problem 

[Mayank Pratap]:
20150612 06:16:50
Finally ....After many TLEs I got AC ... :) 

Aditya Kumar:
20150531 11:13:57
Think simple

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 