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
vish8062: 2020-04-29 10:02:37

@starters12 i also implemented the same in java getting tle

symoon: 2020-04-28 01:19:36

Count divisor between gcd(a,b) in sqrt.

vritta: 2020-04-14 11:44:13

If you r using cin or cout then paste this line in main function first- "ios::sync_with_stdio(0);
cin.tie(0);" . Secondly if u r using sqrt() function for running in loop, then use floor(sqrt()); if u r doing something like- if(floor(sqrt())*floor(sqrt())==z) else u will get W.A.

Last edit: 2020-04-14 12:34:57
shivamvermadev: 2020-04-07 12:46:11

always use scanf and printf for IO operations in spoj questions
Most of them gives TLE with cin and cout

naman_mawandia: 2019-12-29 20:42:46

use printf & scanf instead of cout & cin, costed me 2 TLE

Last edit: 2019-12-29 20:43:54
mrmajumder: 2019-11-30 06:54:04

The trick here is that, the divisors of the gcd(a, b) is the answer [Let a, b be the given pair].
I did sieving to find prime numbers. Used those primes to prime factorize the value of the gcd. Then counted the number of divisors possible.
Use optimized I/O, unless there will be casualties.

rana_1234: 2019-10-29 20:56:00

cout gave me accepted and printf gave me WA. :)

importme: 2019-09-28 21:42:38

My 50th on SPOJ!!

sanket17: 2019-07-13 06:42:47

if u r using cin and cout then copy this lines
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

towhid1zaman: 2019-06-19 06:10:26

find gcd, and dont use printf


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