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
Varun Gambhir:
20150615 12:58:44
All those getting TLE with sqrt(n) approach and using C/C++, use scanf printf instead of cin and cout. 

Harshit:
20150612 07:43:55
Last edit: 20150803 11:12:39 

excursionist:
20150515 22:31:40
Loved it !!


[Lakshman]:
20150310 06:15:02
@Muhammad Annaqeeb: When pyramid cluster was functional the time limit was 6s now the problem has been moved to CUBE cluster, time limit is reduced to 0.6s. As CUBE is 20x times faster than Pyramid. So O(sqrt(gcd(a,b))) can easily pass, it is also recommended to use scanf & printf. 

Muhammad Annaqeeb:
20150309 23:52:17
My sumbmision in C++ was accepted in 20140413 in O(sqrt(gcd(a,b)) , now resubmitting the same submission is TLE. Is the limits now harder than a year ago? Is this on purpose or due to upgrades? can anyone confirm this? Last edit: 20150310 03:50:55 

[Lakshman]:
20150225 19:51:18
What about a new problem with better constraints like 10^14.


deerishi:
20150225 18:13:34
Accepted 0.15s! Easy one if you know the math!! 

tyler_durden:
20150212 09:12:35
@abdelkarim my solution is O(sqrt(gcd(a,b))) and passed in 0.5 seconds 

jaswin kaur:
20150205 21:37:41
got TLE with cin,cout & for loop


Ayon Das:
20150111 12:11:17
anyone who has done NDIV this is just a nice variation.. AC in one go :) :) 
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 