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

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-12-15 18:22:44

my 'tricks' sucessfully make me in first place ;-) after this you may try n-divisors problem with more strict time limit ;-)

Nitin Khanna: 2012-10-24 13:22:35

It seems that 0 <= a <= b <= 1000000

Prakash Murthy: 2012-08-11 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 3-factorful numbers below 100 are
2*2*3*5, 2*3*3*5 & 2*2*3*7

fandi a rahadian: 2011-12-25 07:50:58

can u tell me the answer of
1 1000000 7 please

cegprakash: 2011-12-12 14:05:35

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
Przemys³aw Uznañski: 2011-11-22 01:22:42

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

sandeep pandey: 2011-03-02 18:40:40

Last edit: 2011-03-07 21:30:07
madhav: 2011-02-11 03:22:07

Very trivial problem!

Radhakrishnan Venkataramani: 2011-01-31 15:53:17

Nice Modification to the Original problem :)
But i didn see any problem with T>10000 instead of T<10000

Last edit: 2011-01-31 15:53:59

Added by:gogo40
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