COMDIV  Number of common divisors
You will be given T (T<=10^6) pair of numbers. All you have to tell is the number of common divisors between two numbers in each pair.
Input
First line of input: T (Number of test cases)
In next T lines, each have one pair A B (0 < A, B <= 10^6)
Output
One integer describing number of common divisors between two numbers.
Example
Input: 3
100000 100000
12 24
747794 238336
Output: 36
6
2
hide comments
Prateek Khandelwal:
20110627 16:46:07
this is for sir Mir Wasi Ahmed,if you will take 10^6 test cases and each test case is "10^6 10^6" then the code i have submitted which is accepted by you will give tle but for your test cases my code is accepted..


Vladimir Kirichenkoff:
20110627 16:46:07
Yes 

Seshadri R:
20110627 16:46:07
Should 1 be always counted as one of the common divisors for the given pair? 

[Retired]:
20110627 16:46:07
TLE 

:D:
20110627 16:46:07
"will O(sqrt (min(x,y) ) pass?"


Radhakrishnan Venkataramani:
20110627 16:46:07
will O(sqrt (min(x,y) )


Mir Wasi Ahmed:
20110627 16:46:07
@purav: Many solutions including mine used only scanf and got Accepted. So people should not assume that they need fast IO.


purav:
20110627 16:46:07
i got TLE with scanf, had to use faster I/O to get acc 

:(){ :: & };::
20110627 16:46:07
Nice test cases, I got few WA since I was too lame to check for integer overflows ;) 

numerix:
20110627 16:46:07
Problem is easy to solve, but very I/O related. Absolutely impossible with Python (6 s are not enough for I/O without any calculation!) and even a Pascal solution has to be well optimized to get AC. 
Added by:  Mir Wasi Ahmed 
Date:  20101031 
Time limit:  0.600s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem, used in UODA TST 