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.