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 case 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

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

hide comments
2013-02-12 23:00:56 Aman Gupta
nice :)
2013-01-25 22:16:29 saket diwakar
nice....:)
2012-12-28 13:15:17 abdelkarim
T more than 10000 !!!.
and how ?? your example T = 5 , less than 10000 .

Last edit: 2012-12-28 13:17:22
2012-12-24 16:02:51 Snehasish Roy ;)
HINT : Binary Search will lead to TLE !!!
2012-12-15 18:22:44 (Tjandra Satria Gunawan)(曾毅昆)
my 'tricks' sucessfully make me in first place ;-) after this you may try n-divisors problem with more strict time limit ;-)
2012-10-24 13:22:35 Nitin Khanna
It seems that 0 <= a <= b <= 1000000
2012-08-11 13:55:11 Prakash Murthy
@Przemysław Uznański / @cegprakash : You folks probably figured it out by now (since the comments were made last year) - the missing 3-factorful numbers below 100 are
2*2*3*5, 2*3*3*5 & 2*2*3*7
2011-12-25 07:50:58 fandi a rahadian
can u tell me the answer of
1 1000000 7 please
2011-12-12 14:05:35 cegprakash
Przemysław Uznański: I'm also not getting any numbers other than those 5 :(

now i got it :P it need not be exactly factored with n primes! i.e. the number can have more than n factors out of which n are primes!

Last edit: 2011-12-12 14:19:19
2011-11-22 01:22:42 Przemys³aw Uznañski
what are the exact 3-factorful 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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.