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 case 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
Aman Gupta:
20130212 23:00:56
nice :) 

saket diwakar:
20130125 22:16:29
nice....:) 

abdelkarim:
20121228 13:15:17
T more than 10000 !!!.


Snehasish Roy ;):
20121224 16:02:51
HINT : Binary Search will lead to TLE !!! 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121215 18:22:44
my 'tricks' sucessfully make me in first place ;) after this you may try ndivisors problem with more strict time limit ;) 

Nitin Khanna:
20121024 13:22:35
It seems that 0 <= a <= b <= 1000000 

Prakash Murthy:
20120811 13:55:11
@Przemysław Uznański / @cegprakash : You folks probably figured it out by now (since the comments were made last year)  the missing 3factorful numbers below 100 are


fandi a rahadian:
20111225 07:50:58
can u tell me the answer of


cegprakash:
20111212 14:05:35
Przemysław Uznański: I'm also not getting any numbers other than those 5 :(


Przemys³aw Uznañski:
20111122 01:22:42
what are the exact 3factorful numbers <=100? I can name 5 of them, not 8: 2*3*5,2*3*7,2*3*11,2*3*13,2*5*7 
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 