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
2017-01-24 15:17:58
NIce one simple at first look but indeed not :)
2017-01-19 19:31:16
Tonnes of optimizations finally got AC in 0.03........#1 in the c++14 and #4 in overall rankings:D

Last edit: 2017-01-21 07:11:59
2016-12-28 07:55:29
Modified sieve + Precomputation ...
TLE :( ->->-> AC :)
2016-10-15 19:41:47
USed lower and upper bound stl and stored in Map.My 50th :)
2016-10-05 00:59:22
modified sieve + precomputation => AC in 0.18 sec
2016-07-17 11:57:19
nice implementation of sieve and memorization :)

2016-07-06 20:52:55 Deepak
finally AC : ) ....in .12.
2016-04-03 19:37:16
modified sieve ... may be nothing else...
2016-03-12 21:21:08
SUCH A NICE PROBLEM...GET AC AFTER 5-6 attempts
2016-03-05 16:47:59
AC in one go!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.