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: 2022-12-20 08:38:04

There are only 101 different divisors values: 1,3,5,...,1215,1323. I used smallest prime factors to speed up factorization.
One more test case:
1
231 1 10000000000
52

kabbo25: 2020-05-02 13:25:43

prime_factorization+upper_bound+lower_bound
pre calculation

zakir068: 2020-03-14 06:16:05

Just one observation did the trick

tarungupta: 2019-05-11 08:30:15

Must do problem! For help you can refer my repository "Spoj-Solutions" on github.com/12tarun

nuhash_40: 2018-04-21 04:36:30

if wa try this
2
1 2 4000000
1 1 4000000

Last edit: 2018-04-21 04:36:37
sy_117: 2018-04-06 16:07:05

Finally removed from TODO list after 2 yr 3 months :)

Last edit: 2018-04-06 16:07:22
karthik1997: 2018-01-05 13:34:03

Pre Computation is the key for optimisation . AC 0.01s
Fast I/O , Prime Factorization in O(log(N) ) , and binary search does the trick . Complexity : O(NlogN) where N is 10^5 . Good Luck :)

Last edit: 2018-01-05 13:34:28
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


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