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
JordanBelfort: 2014-03-17 21:15:11

no binary search think simple

harsh: 2014-01-20 06:10:25

binary_search()..:).

shuvo karmakar: 2013-12-18 21:07:55

0

cegprakash: 2013-12-12 20:38:38

A must do. Superb problem!

demon: 2013-09-23 17:27:28

Good one :)

Aman Gupta: 2013-02-12 23:00:56

nice :)

saket diwakar: 2013-01-25 22:16:29

nice....:)

abdelkarim: 2012-12-28 13:15:17

T more than 10000 !!!.
and how ?? your example T = 5 , less than 10000 .

Last edit: 2012-12-28 13:17:22
Snehasish Roy ;): 2012-12-24 16:02:51

HINT : Binary Search will lead to TLE !!!


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