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
viniet_sw: 2018-01-02 15:14:00

bhosadi waalo ac in one go ka kya show off krte rehte ho gand utha ke har jagah

sanyam19: 2018-01-02 14:48:23

AC in 1 go :)

karthik1997: 2017-12-27 16:39:58

Man , Never thought i would end up with fastest submission till date ( 0.10s )
Fast I/O + sieve_modified + binary_gcd + O( log(N) ) +factorization method for number of divisors got me this :)

Last edit: 2017-12-27 20:04:49
chetan4060: 2017-12-19 18:25:20

use sieve first then gcd
AC in one go:-)

sirjan13: 2017-11-02 21:22:19

50th =)
Be Careful with I/O.Cheers!

madhur4127: 2017-10-04 15:04:19

If TLE: use || ios::sync_with_stdio(0); cin.tie(0); || in C++ to make I/O fast.
If WA check for factorization error for (38,76) or other such cases.

naveen_4199: 2017-09-27 17:42:22

use scanf and printf to resolve TLE error along with better mathematical logic

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


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