You will be given T (T ≤ 10⁶) pairs of numbers. All you have to tell is the number of common divisors between the 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⁶)

Output

One integer describing number of common divisors between two numbers.

Example

Input:
3
100000 100000
12 24
747794 238336

Output:
36
6
2