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
tle_infinite1:
20220829 17:23:57
1. ___gcd(a,b)


ive1010:
20220212 12:05:28
find prime divisors of the gcd(a,b) using seive, 

hieroph4nt:
20210811 09:51:36
weak test cases i guess! O(T * sqrt(gcd(a, b))) passes the test cases. It should be 10 ^ 6 * 10 ^ 3 in worst case. O(T * log(gcd(a, b))) good approach tho. 

ishraaq_56789:
20210608 16:08:39
Important  1 is also considered a factor. It cost me a wrong answer. 

vipvipul12:
20210519 11:23:29
Use "\n" instead of endl to avoid TLE. 

akshat_19:
20210511 13:56:15
AC in one go. No scanf,printf used. Complexity>O(logn + sqrt(n)) 

daredevil666:
20210324 13:06:02
I got an AC without using scanf and printf 

princemishra:
20201022 08:21:22
used gcd and prime factorization with int, scanf , printf and finally got AC with total complexity log(N) + sqrt(N).


md_yasin:
20200604 08:47:25
used precalculation of number of divisors. but got 3 tles for using cin and cout.


landi58:
20200430 15:50:54
1. paste this line in main function first "ios::sync_with_stdio(0);

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 