COMDIV - Number of common divisors

no tags 

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
mdsharique: 2015-12-21 07:59:47

atlast AC after several TLE

Prateek Agarwal: 2015-12-12 14:34:40

Very Tight Time limit. AC in c++ but TLE in python.
Anyone whose result passed in python?

ram_1897: 2015-09-25 09:21:26

use euclidean algorithm to compute gcd :)

Abdulsalam Abdo Helal: 2015-09-15 14:30:30

scanf and prinf is recommended to pass time

Abishek: 2015-09-10 10:00:03

fast i/o and basic math !

Medo: 2015-08-20 16:03:11

If you are sure of your complexity. Change to Printf scanf, and make sure all your variables are declared as int not long long.

prakash_reddy: 2015-08-18 15:56:38

Nice problem.... :)

sy_117: 2015-08-15 16:04:40

AC in first go.....Basic Math nothing else!

Indian Cyber Army (IndiShell): 2015-08-08 11:16:29

My code is running perfectly on Dev C++ but here its showing runtime error with floating point exception. I have used long long int. can you please point out the error to me.
http://ideone.com/NNBjLe

Sue: 2015-06-25 11:55:55

AC in the first go ~
use printf scanf ~


Added by:Mir Wasi Ahmed
Date:2010-10-31
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