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
nuhash_40:
20180421 04:36:30
if wa try this


sy_117:
20180406 16:07:05
Finally removed from TODO list after 2 yr 3 months :) Last edit: 20180406 16:07:22 

karthik1997:
20180105 13:34:03
Pre Computation is the key for optimisation . AC 0.01s


aman224:
20170303 11:10:57
Awesome problem...


rohith_rax:
20170206 23:01:03
its says time limit exceeded . any hint pls ..


visvats_141095:
20160623 00:46:39
perfect use of STLs ! :D


SUBHAM SANGHAI:
20160527 13:53:22
Very nice problem.. seems easy,but much of optimisation required..binary search helped 

xMAn:
20160512 19:40:50
only perfct squares have odd no. of divisors .. 

Jamil Siam:
20160328 06:03:17
awesome problem!


Govind Lahoti:
20151214 17:58:16
lot of optimizations needed. Learnt a lot. Nice problem :) 
Added by:  John Rizzo 
Date:  20081004 
Time limit:  0.449s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  AlKhawarizm 2008  Set by eleusive 