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

frochbg: 2019-05-30 20:07:31

Nice problem :)

scolar_fuad: 2019-04-13 15:42:27

Only a single cin and cout will cost you TLE don't need to seive just find gcd and then count divisor

happy coding

Muhammad Annaqeeb: 2019-04-09 17:54:13

Here is a note about comparing the same solution speed across different programming languages:
C++ with non-optimized cin and cout ---Time Limit Exceeded
C++ with optimized cin and cout -- 0.32 second
Java with non-optimized IO -- Time Limit Exceeded
Java with optimized IO -- 0.52 second
Free Pascal with non-optimized IO -- 0.34 second


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