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

suraj1611: 2019-03-18 19:48:13

using scanf and printf instead of cin and cout could help!

sahilsinghss: 2019-03-18 17:47:12

WTH How can using cout instead of printf cost a WA

Last edit: 2019-03-18 17:47:35
midoriya: 2019-03-15 12:01:22

I don't what to do anymore --- should I use cin, cout or scanf ,printf

harry_shit: 2019-02-12 10:59:06

this was wayy more easy than i thought,
O(sqrt(gcd(a,b)))

raghav6: 2019-01-11 13:00:54

Just use scanf and printf for I/O , avoid cin & cout in C++ costed me TLE.

duet_cse16: 2018-10-30 08:55:54

What's the application of gcd in this problem??

saketag007: 2018-10-14 17:50:59

AC in 3rd go , just use fast input/output , no need to build sieve , just find factors for every test case in O(sqrt(n))

Last edit: 2018-10-14 17:51:15

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