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
sarelfeniel: 2014-08-22 22:44:46

Easy problem but I/O is a huge bottleneck.

: 2014-07-22 20:10:39

fu*king cin && cout :( getting tle wid same code :P

surayans tiwari(http://bit.ly/1EPzcpv): 2014-07-12 11:56:53

after 5 w.a finally accepted in 1.54 sec :D

Kanav Vats: 2014-07-11 15:08:39

Easy...careless mistake costed me 2 WA :(

Branimir Ri├Ęko: 2014-06-22 18:00:38

Is 0 a divisor?? :)

arp_ee: 2014-06-09 20:28:28

nice question..learnt a new thing.

[Lakshman]: 2014-03-29 10:16:11

Now on TOP.

[Lakshman]: 2014-03-29 06:37:44

@Hassan Azzam You are getting TLE not because of scanf or printf it is your naive algo.the worst case complexity is O(sqrt(gcd(a,b))).

Last edit: 2014-03-29 06:38:00
Hassan Azzam: 2014-03-29 00:21:27

problem needs to be burnt -_-
Despite using Scanf & int , i always get TLE.

Bharath Reddy: 2014-03-28 09:35:55

cin and cout gives TLE.
scanf,printf --> AC


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