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
ANKUR GARG: 2013-01-28 12:44:03

can u give some more tricky test cases as these are working fine in my code but m still getting WA

Darky: 2013-01-20 11:41:52

@Arunesh Pandey: 1

Arunesh Pandey: 2013-01-20 09:29:50

what will be the output for 3 13 ?

dipak yadav: 2013-01-19 13:30:11

my id is 8535685
why WA

Last edit: 2013-01-19 13:32:19
dipak yadav: 2013-01-19 13:24:44

what is wrong in my code id is 8535685
why Wa

Spar!k: 2013-01-15 15:37:11

Last edit: 2013-02-02 22:49:11
DEVANSH PARASHAR: 2013-01-01 20:55:09

tle

Retaliation: 2012-12-31 20:40:41

check my solution. Why am i getting tle ? submission id :-8386786

spock: 2012-06-21 03:37:36

finally..green light.. :P

krishnan: 2012-02-04 12:23:47

Atlast I got AC

Last edit: 2012-02-04 12:25:03

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