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
siddhant gupta: 2014-01-23 13:17:53

do not use cin or cout. it wil give tle. wasted my 2 hrs on such a easy ques.

Last edit: 2014-01-23 13:18:05
I am back: 2014-01-10 17:55:09

easy one AC in first attempt

Vipul Pandey: 2014-01-04 20:53:54

Got AC in 1st attempt! Easy one! took only 15 minutes.

Archangel: 2013-12-25 05:16:11

i am getting WA pls help someone
http://ideone.com/4wIiKP

Himanshu: 2013-10-17 17:53:24

simple mathematics

P_Quantum: 2013-09-20 17:57:37

AC with O(sqrt(gcd(a,b))).. !!

Mahesh Mishra: 2013-09-17 09:18:47

dont use long long and cin cout .. it will time out

Prakhar Gupta: 2013-08-10 12:54:45

Is 0,0 also a test case....i m gettin WA while it run perfectly on ideone....my id 9812939

p.s. accepted

Last edit: 2013-09-16 08:50:46
: 2013-08-02 13:14:20

nice1 my 100th on spoj :D

Nishant Gupta: 2013-07-24 13:09:51

complexity O(sqrt(gcd(a,b))


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