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
mkfeuhrer: 2016-06-12 11:48:48

terribly silly ...... use scanf/printf !! costed me WA! easy eucledian gcd

jitendrakk: 2016-06-12 11:37:32

Never using cin & cout again.. :(

pranjalikumar9: 2016-06-02 19:35:19

std::__gcd(n,k) and printf/scanf pave the way for ac!! :)

aru_674: 2016-05-22 20:14:47

calculating gcd with euclidean gave tle but with std::__gcd(n,k) ac

saketj: 2016-05-14 14:59:38

TLE when using cin and cout but got AC on using printf and scanf..

killjee_15: 2016-03-24 19:36:49

sometimes thinking too much is dangerous :( 2 TLEs for too much thinking

ghost_wire: 2016-02-08 19:20:42

easy one for c++
to increase input and output speed try this:
ios::sync_with_stdio(false);
cin.tie(0);

Govind Lahoti: 2016-01-26 17:36:51

use scanf/printf

nonushikhar: 2016-01-23 22:01:40

easy ac in one go :)

dwij28: 2016-01-10 11:44:05

Woo.. Fast input too takes 0.36 seconds.. O(sqrt(gcd(a, b)) using the std::__gcd available in C++.. Any hint on how to make it faster ??

Last edit: 2016-01-11 17:06:33

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