Given two integers A and B, find the count of divisors of A which also divides B.

Input

• First line contains an integer T which denotes the number of testcases.
• Next T lines contains two integers A and B.

Output

Print the count of common divisors on a new line.

Constraints

• 1 <= T <= 500000
• 1 <= A, B <= 1000000

Note: Large input/Output files, so use scanf/printf.