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
2020-03-03 23:04:09
AC in one attempt :)
2019-11-05 21:13:39
Excellent question!!! Great use of sieve.
2019-07-18 19:30:49
@rajat813 these are the 6 integers
30 42 60 66 70 78 84 90
2019-03-14 00:45:51
how answer of
1 100 3 is equal to 8
2018-03-22 23:05:44
I've got a O(T+(X*root(X)) approach where X=10^6. Used preprocessing memoization. I've got an AC @1.18 secs but I see people with quite less runtimes ~<0.5secs. Whats the approach for it?
2017-12-04 07:38:29
AC in one go
2017-06-16 21:47:54
Sieve + BIT ..:)
2017-05-28 03:05:13
AC in 0.06 sec .......use upper & lower bound stl.......
2017-03-01 08:44:22 shahzada
Just Precomputation.
2017-01-24 16:35:36
tle at first but then precomputation came to rescue..:)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.