SPOJ.com - Problem VDATE

VDATE - Flirtatious Verma

Harsh Verma is a college guy who likes to date a lot of girls. He has got great flirting skills and he managed to convince a lot of girls to go out with him. He knows X dating locations in his city. He wanted to date all the girls so he started assigning each of them some dating locations. He treated all girls equal so he gave each of them equal number of dating locations. He wanted to spend maximum possible time with each girl so he tried to maximise the number of dating locations given to each girl. Also, no two girls got the same dating location.

After the distribution, he was left with Y dating locations. But unfortunately, he was too excited and he forgot to count the number of girls he had already assigned the dating locations . This was a difficult situation for him but Aditya (Sciencepal) came to his rescue. He gave him a list of possible number of girls to him which would help him to figure out the actual number of girls. Your task is to write a program to find the total count of possible number of girls i.e. the number of entries in the list prepared by Sciencepal.

If there are infinite possibilities, print -1. If there is no solution, print 0.

Input

First line will contain an integer T i.e. the number of test cases. (1 ≤ T ≤ 50)

Next T lines will contain two integers X and Y. (0 ≤ X ≤ 1000000000, 0 ≤ Y ≤ 1000000000)

Output

For each test case, print a single integer denoting the count of possible number of girls.

Example

Input:
1
14 2

Output:
4

Explanation

If X = 14 and Y = 2 then the possible number of girls are 3, 4, 6 and 12.

Submit solution!

Added by:	DJ
Date:	2017-07-12
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	College contest

hide comments

2024-03-09 02:49:03
Hi... I ran the exact same code in rust and c++, given an accepted answer in the latest one and a incorrect answer on the rust one... Does this indicate any error on my part? Or maybe is it an error with the input file?

2017-12-28 22:40:25 Addy
When will there be infinite possibilities?

2017-09-30 14:09:01
Excellent problem! The core bit of the algorithm is something I was reluctant to implement properly for too long, and skipped many similar problems where I knew it was required to pass - this one tricked me to finally do it right =) A lot can go wrong though! Feels great to get AC with Python here.

Vladimir: check for anything involving 0, 1, primes, cover all relations between x and y (it's ugly).
dhana_25796: consider why there are some locations left after distribution.

2017-07-21 03:10:03
who can tell me the O(n) of the probem?

2017-07-18 05:25:44 Vladimir
Any tricky test cases? Can't understand why I keep getting WA :(

2017-07-16 07:29:35
For the given sample test case why can't the no of girls be 1 or 2? ie the possible count can be 1,2,3,4,6,12?

2017-07-15 16:02:55
@visleck Consider x = 21, y = 5. Answer should be 2.

Last edit: 2017-07-15 16:04:42

2017-07-14 21:17:12
@divyanshjr i believe i am doing it correctly.... can u give a sample case where i am going wrong??
(edit) Thank you very much divyansh

Last edit: 2017-07-22 21:55:56

2017-07-13 17:01:58
@aman224 For x < y, it will be an invalid case with no solution, so expected answer is 0 as mentioned in the problem statement. NZEC problem for JAVA has been fixed.

Last edit: 2017-07-13 19:37:39

2017-07-13 16:17:29
@DJ please fix the following issues with this problem:-
1. Exactly same code passes in C, gets an RTE in JAVA :/ , maybe there is something wrong with the input files.
2. According to the problem statement ("After the distribution, he was left with Y dating locations") , Y should always be <=X as pointed by shubham2305 :p.