ODDDIV - Odd Numbers of Divisors


Given a positive odd integer K and two positive integers low and high, determine how many integers between low and high contain exactly K divisors.

Input

The first line of the input contains a positive integer C (0 < C < 100,000), the number of test cases to follow. Each case consists of a line containing three integers: K, low, and high (1 < K < 10000, 0 < low ≤ high < 10^10). K will always be an odd integer.

Output

Output for each case consists of one line: the number of integers between low and high, inclusive, that contain exactly K divisors.

Example

Input:
3
3 2 49
9 1 100
5 55 235

Output:
4
2
1

hide comments
BLANKRK: 2013-09-22 14:43:06

finly finly done!!!

tantu92: 2013-02-11 14:32:51

more test cases plz...

DivineAtheist: 2013-01-14 22:13:24

finally got AC!! nice problem..:)

Snehasish Roy ;): 2012-12-23 15:48:49

Awesome problem :)


Added by:eleusive
Date:2008-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2008 - Set by eleusive