Tanya has recently learned about Euler's totient function. So she started solving problems on it to clear her concepts. But she got stuck on a problem and asks for your help. Tanya defines the problem as follows:

Given two integers "A" and "B", you have evaluate the value of F(A,B).

F(A,B) is defined as the summation of all phi(k) if k divides both "A" and "B". where phi(k) is Euler's totient function.

Help Tanya to compute the value of F(A,B).

Input:

First line contains an integer "t" , denoting the number of test cases.

Each test case has only line and contains two integer "A" and "B" , separated by a space.

Output:

Print the value of F(A,B) for each test case in a new line.

Constraints:

1 <= t <= 10^3

1 < A,B <= 10^5