Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3483.   Common Divisor
Time Limit: 2.0 Seconds   Memory Limit: 65536K
Total Runs: 2615   Accepted Runs: 1042



Given two positive integers n and m, write a program to calculate the number of commen divisors of them.

Input

The first line of input is the single integer t, given the number of test cases. Then t lines follows, each line has two positive integers: n and m. (0 < t ≤ 1000, 0 < n, m ≤ 2147483647).

Output

For each test cases, output an integer in a single line: the number of common divisors of the given n and m.

Sample Input

3
5 15
20 30
32 56

Sample Output

2
4
4



Source: TJU Team Selection Contest 2010 (1)
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop