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
2016-02-05 13:25:15 minhthai
such a nice problem! Be careful with your "limit" though :)
2016-01-06 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 i-o, 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.
2015-12-01 01:22:50 Md.Mahmudul Hasan
use 2d vector and push number in vector like vector[ factor] .push_back(number) and find upper bound and lower bound and res=upper_bound-lower_bound.
2015-10-27 10:38:37 SangKuan
Great problem
2015-10-20 06:41:12 newbie
Got AC in 0.64.
TIP: GUYS BEWARE OF n=0.
2015-08-24 10:05:54
Wonderful Problem =D
Just Apply memorization DP :)
2015-06-27 22:08:14 :.Mohib.:
Very Nice problem!!
2015-06-26 10:11:17 kp
learnt a lot.. awesome problem
2015-06-12 06:16:50 [Mayank Pratap]
Finally ....After many TLEs I got AC ... :)
2015-05-31 11:13:57 Aditya Kumar
Think simple
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.