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
Prateek Khandelwal: 2011-06-27 16:46:07

this is for sir Mir Wasi Ahmed,if you will take 10^6 test cases and each test case is "10^6 10^6" then the code i have submitted which is accepted by you will give tle but for your test cases my code is accepted..

Reply: Time limit was set considering the different range of a and b. I don't think whole input should contain the worst case. If you look at the submission statistics you'll see the number of TLEs, so data is not that weak. However, if you think you got lucky then enjoy it. :)

Mir Wasi Ahmed

Last edit: 2011-02-08 11:00:26
Vladimir Kirichenkoff: 2011-06-27 16:46:07

Yes

Seshadri R: 2011-06-27 16:46:07

Should 1 be always counted as one of the common divisors for the given pair?

[Retired]: 2011-06-27 16:46:07

TLE

:D: 2011-06-27 16:46:07

"will O(sqrt (min(x,y) ) pass?"
It's pretty unlikely.

Radhakrishnan Venkataramani: 2011-06-27 16:46:07

will O(sqrt (min(x,y) )
pass?

Mir Wasi Ahmed: 2011-06-27 16:46:07

@purav: Many solutions including mine used only scanf and got Accepted. So people should not assume that they need fast IO.

Sorry to People using some of the slower languages. It seem there is no way I can set different time-limits for different languages.

Last edit: 2010-11-03 14:39:15
purav: 2011-06-27 16:46:07

i got TLE with scanf, had to use faster I/O to get acc

:(){ :|: & };:: 2011-06-27 16:46:07

Nice test cases, I got few WA since I was too lame to check for integer overflows ;-)

numerix: 2011-06-27 16:46:07

Problem is easy to solve, but very I/O related. Absolutely impossible with Python (6 s are not enough for I/O without any calculation!) and even a Pascal solution has to be well optimized to get AC.


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