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
anksjain:
20201205 13:13:53
TIP > use scanf and printf FOR C++ ( sive and smallest prime factor ) 

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).


ridhish_jain:
20201007 19:38:01
using linear sieve + prime factorization(logn)time


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


jyoti369:
20200516 08:34:04
*** JAVA TIPS


coder_ahmed:
20200515 14:02:52
Used Linear sieve+gcd(a, b) + "ios::sync_with_stdio(false); cin.tie(0)..." but STILL TLE 

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


vish8062:
20200429 10:02:37
@starters12 i also implemented the same in java getting tle 

starters12:
20200429 09:39:31
used linear sieve+gcd+precompute divisors..still get tle using java


symoon:
20200428 01:19:36
Count divisor between gcd(a,b) in sqrt. 
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 