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
prabodh prakash: 2017-05-03 21:51:19

cout, cin gave me few TLE and then god knows what gave me WA - finally correct !

aditya9125: 2017-03-21 16:19:01

Using cin,cout along with fast ip/op passed in every problem I have solved so far,so never used scanf,printf in a C++ code, but here I don't know why using scanf,printf becomes a compulsion.This thing annoys me a lot.If anyone can help,pls help me know that what's the use of "ios_base::sync_with_stdio(false); cin.tie(NULL) in a c++ code" if we always have to use scanf,printf

Last edit: 2017-03-21 16:19:59
rohit9934: 2017-03-11 14:23:17

AC in 1 go with c++ cin,cout working fine in 0.35 sec

epsilonalpha: 2017-03-07 17:38:51

Lovely concept! Initially I was brute-forcing but the comments were really helpful!
Note: Large I/O. Use IO Optimization tricks.
AC in 0.27s in C++.
Also my 100th. :)

simran07: 2017-02-26 05:59:36

i hate when it gives tle due to cin cout.......

cake_is_a_lie: 2017-02-15 09:20:09

EDIT: FYI for C++ users
- ios_base::sync_with_stdio(false)
- cin.tie(nullptr)
- never use std::endl; use '\n' instead
=> cin/cout is faster than scanf/printf (tested on this problem);

Simple problem, bad constraints - it's really testing how fast your input library is more than how fast your core algorithm is AND there's no warning about the large input. Thumbs down.

Last edit: 2017-02-15 09:41:38
kg93999: 2017-01-14 18:15:14

java = TLE
c++ = AC :(

subodra_9: 2016-12-25 20:47:13

100th =D ... #printf/scanf

davidgalehouse: 2016-10-13 03:12:26

Cool, for C# I can't even parse the input without a TLE.

suvro_datta: 2016-09-20 13:03:27

try this one with spoj input 4 16 output: 3


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