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
Mir Wasi Ahmed: 2011-06-27 16:46:07

@A. Muh. Primabudi: Sorry, At first I uploaded a test data different from the original one by mistake. Now I replaced the data and re-judged every solution. Sorry for the inconvenience.

A. Muh. Primabudi: 2011-06-27 16:46:07

what the hell? i getting AC last morning,
but now my accepted program is TLE.

The Champ: 2011-06-27 16:46:07

got AC :)

Last edit: 2010-11-01 16:07:33
well i am lagging: 2011-06-27 16:46:07

this problem is not clear as lower limit of the numbers is not given?

Edit: Fixed

Last edit: 2010-11-01 17:35:53

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