Common Divisors Count

You are given two integers n and m. Your task is to find the number of common divisors between them. A number d is a common divisor of n and m if and only if it divides both numbers, i.e. $$n \bmod d = 0$$ and $$m \bmod d = 0$$.

It is a well-known fact that the number of common divisors of n and m is equal to the number of divisors of $$\gcd(n,m)$$ where $$\gcd$$ denotes the greatest common divisor. For example, given n = 12 and m = 18, the greatest common divisor is 6 and its divisors are 1, 2, 3, and 6, so the answer is 4.

You are required to read input from standard input and output the results to standard output for each test case.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the next T lines contains two integers n and m separated by space.

Constraints:

• 1 ≤ T ≤ 10⁴
• 1 ≤ n, m ≤ 10⁶

outputFormat

For each test case, output a single line containing the number of common divisors of n and m.

## sample

3
12 18
100 75
7 13

4
3
1

</p>