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
2015-05-30 21:50:40 kartikay singh
AC with 0.09s :)

Last edit: 2015-05-30 21:52:21
2015-03-24 11:07:31 Madhav
A great problem...Many concepts involved....
2015-01-17 16:11:23 sparrow
nice problem....

--edit(Francky)--> spoiler removed. Please read the notes below and apply them. Thanks in advance for the next time you'll propose a comment.

Last edit: 2015-01-17 16:12:38
2014-08-26 18:52:15 John and the cows
well, it's seem there are more than 10^5 test cases
2014-03-17 21:15:11 JordanBelfort
no binary search think simple
2014-01-20 06:10:25 harsh
binary_search()..:).
2013-12-18 21:07:55 shuvo karmakar
0
2013-12-12 20:38:38 cegprakash
A must do. Superb problem!
2013-09-23 17:27:28 demon
Good one :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.