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
flipster: 2013-07-23 15:29:46

cake walk:)

Pranye Mawai: 2013-07-20 09:18:17

enjoyd doin it ... :D

tamed: 2013-07-13 19:48:56

@ps my id 9651682 why i m not getting output and why i m also getin wrong answer

Hasil Sharma: 2013-06-17 19:17:43

I don't know why I am getting WA while using C , I have used correct logic int type for all the digits and double for storing sqrt of gcd :/
W.A Finally :)

Last edit: 2013-06-30 20:44:39
Anick Saha: 2013-05-25 17:50:02

long long to int , cinto scanf ... then it gets AC :-/

Shubham Sharma: 2013-05-16 19:01:43

SIGSEGV in my code ..
Submission id : 9278917 plz help

: 2013-04-18 04:22:21

Last edit: 2014-02-27 07:50:28
Eduardo Nunes: 2013-04-16 23:13:03

really nice one, try using gcd ;-D
90th :-)

Meraj Ahmed: 2013-02-04 13:45:58

Mir Wasi Ahmed, please check and tell what is wrong with my solution.
id: 8652675

got it!

Last edit: 2013-12-26 18:46:14
Spar!k: 2013-02-02 22:49:42

AC with scanf/printf


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