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
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!!

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 :) :)


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