## 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
 < Previous 1 2 Next > aman224: 2017-03-03 11:10:57 Awesome problem... Number theory + Binary Search AC @0.03s rohith_rax: 2017-02-06 23:01:03 its says time limit exceeded . any hint pls .. visvats_141095: 2016-06-23 00:46:39 perfect use of STLs ! :D SUBHAM SANGHAI: 2016-05-27 13:53:22 Very nice problem.. seems easy,but much of optimisation required..binary search helped xMAn: 2016-05-12 19:40:50 only perfct squares have odd no. of divisors .. Jamil Siam: 2016-03-28 06:03:17 awesome problem! AC at 0.09s after lots of TLE :D Govind Lahoti: 2015-12-14 17:58:16 lot of optimizations needed. Learnt a lot. Nice problem :) Glenda Emanuella Sutanto: 2015-06-07 05:21:43 Last edit: 2015-06-07 05:25:26 ISHANI: 2014-12-26 13:27:00 My First Vector problem

 Added by: John Rizzo Date: 2008-10-04 Time limit: 0.449s 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