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
tyler_durden: 2015-02-12 09:12:35

@abdelkarim my solution is O(sqrt(gcd(a,b))) and passed in 0.5 seconds

jaswin kaur: 2015-02-05 21:37:41

got TLE with cin,cout & for loop
AC with printf,scanf & while loop
whyyy??

Last edit: 2015-06-24 06:09:04
Ayon Das: 2015-01-11 12:11:17

anyone who has done NDIV this is just a nice variation.. AC in one go :) :)

sarelfeniel: 2014-08-22 22:44:46

Easy problem but I/O is a huge bottleneck.

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

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