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 possiblities, 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
nadstratosfer:
20170930 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.


anurag garg:
20170723 14:07:31
Last edit: 20170813 20:38:43 

arthur1991:
20170721 03:10:03
who can tell me the O(n) of the probem? 

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

dhana_25796:
20170716 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? 

divyanshjr:
20170715 16:02:55
@visleck Consider x = 21, y = 5. Answer should be 2. Last edit: 20170715 16:04:42 

visleck:
20170714 21:17:12
@divyanshjr i believe i am doing it correctly.... can u give a sample case where i am going wrong??


divyanshjr:
20170713 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: 20170713 19:37:39 

aman224:
20170713 16:17:29
@DJ please fix the following issues with this problem:


visleck:
20170712 22:10:29

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