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
Harpreet Singh Khurana: 2012-01-19 08:37:00

can somebody give some more test cases with boundary cases included......is (0,0) also included

Last edit: 2012-01-19 08:37:52
Albert Chen: 2011-11-28 20:17:32

************Warning***********
Very IO related!!!
I used very naive algorithm and got TLE using cin/cout, but accepted with scanf/printf!!!!!!

Hazem: 2011-11-09 22:48:15

i use
O(n/2 + lnln(n)) in c++
and tle!!!!!!!!!!!!!!!!!!!!!!!

??????????????: 2011-11-08 07:22:52

when checking upto (min(a,b))/2 TLE is coming.plz.somebody help me

ontole: 2011-10-31 16:43:33

sqrt(min(a,b)) is giving tle!!!

Yasser Kamel: 2011-10-06 16:49:29

i spend a day for this :
cin and cout did not work

sri: 2011-10-05 19:47:39

O(sqrt(min(x,y)) is getting TLE???
somebody guide me

Dante is not a Geek: 2011-07-13 14:11:10

Can you give a test case where my code fails? I do not understand why there can be overflow for such small numbers. Submission ID: 5374241

Last edit: 2011-07-14 01:10:56
Psycho: 2011-06-27 16:46:07

@radhakrishnan u r comparing it wit finding prime which can be done in (sqrt(n)) but here, I think its solution requires at least O(min(x,y)) time correct me if i am wrong

Egor: 2011-06-27 16:46:07

Solution with 0(n/2 + lnln(n)) is ok on pascal =)
without any optimization

Last edit: 2011-02-16 16:04:49

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