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
smso:
20221220 08:38:04
There are only 101 different divisors values: 1,3,5,...,1215,1323. I used smallest prime factors to speed up factorization.


kabbo25:
20200502 13:25:43
prime_factorization+upper_bound+lower_bound


zakir068:
20200314 06:16:05
Just one observation did the trick 

tarungupta:
20190511 08:30:15
Must do problem! For help you can refer my repository "SpojSolutions" on github.com/12tarun 

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

Added by:  eleusive 
Date:  20081004 
Time limit:  1s 
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 