VDATE - Flirtatious Verma

no tags 

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 Tongue out. 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.


hide comments
Vipul Srivastava: 2017-07-12 22:03:40

Please remove the comments, they are giving away the logic

divyanshjr: 2017-07-12 21:28:48

@shubham2305: Any value is possible.

shubham2305: 2017-07-12 21:20:10

Is X>=Y OR any value possible??

harsh_verma: 2017-07-12 18:37:40

@dazzler as if it was 1 then max no of cities will be assigned to it will be all 14 and not 12.

dazzler__: 2017-07-12 18:31:00

thnx..flirtious verma

Last edit: 2017-07-12 18:43:50

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