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
sy_117: 2015-08-15 16:04:40

AC in first go.....Basic Math nothing else!

Indian Cyber Army (IndiShell): 2015-08-08 11:16:29

My code is running perfectly on Dev C++ but here its showing runtime error with floating point exception. I have used long long int. can you please point out the error to me.
http://ideone.com/NNBjLe

Sue: 2015-06-25 11:55:55

AC in the first go ~
use printf scanf ~

Varun Gambhir: 2015-06-15 12:58:44

All those getting TLE with sqrt(n) approach and using C/C++, use scanf printf instead of cin and cout.

Harshit: 2015-06-12 07:43:55

Last edit: 2015-08-03 11:12:39
excursionist: 2015-05-15 22:31:40

Loved it !!
AC in first go..!! xD

Last edit: 2015-06-24 06:08:26
[Lakshman]: 2015-03-10 06:15:02

@Muhammad Annaqeeb: When pyramid cluster was functional the time limit was 6s now the problem has been moved to CUBE cluster, time limit is reduced to 0.6s. As CUBE is 20x times faster than Pyramid. So O(sqrt(gcd(a,b))) can easily pass, it is also recommended to use scanf & printf.

Muhammad Annaqeeb: 2015-03-09 23:52:17

My sumbmision in C++ was accepted in 2014-04-13 in O(sqrt(gcd(a,b)) , now resubmitting the same submission is TLE. Is the limits now harder than a year ago? Is this on purpose or due to upgrades? can anyone confirm this?

Last edit: 2015-03-10 03:50:55
[Lakshman]: 2015-02-25 19:51:18

What about a new problem with better constraints like 10^14.

(Francky) => There's yet a very recent problem with similar method and constraints. So no.

(Lakshman)-->Okay No problem.

Last edit: 2015-02-26 04:05:21
deerishi: 2015-02-25 18:13:34

Accepted 0.15s! Easy one if you know the math!!


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