You are given two integers a and m. Calculate the number of integers x such that 0 ≤ x < m and \gcd(a, m) = \gcd(a + x, m).

Note: \gcd(a, b) is the greatest common divisor of a and b.

Input

The first line contains the single integer T (1 ≤ T ≤ 50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and m (1 ≤ a < m ≤ 10^{10}).

Output

Print T integers — one per test case. For each test case print the number of appropriate x-s.

Example

Input


3
4 9
5 10
42 9999999967


Output


6
1
9999999966

Note

In the first test case appropriate x-s are [0, 1, 3, 4, 6, 7].

In the second test case the only appropriate x is 0.
def gcd(x,y):
    if x==0 or y==0:
        return max(round(x),round(y))
    elif x>y:
        return gcd(round(x%y),round(y))
    else:
        return gcd(round(x),round(y%x))

def fi(x):
    fac=[]
    remain=round(x)
    res=round(x)
    if round(remain%2)==0:
        fac.append(2)
        while round(remain%2)==0:
            remain=round(remain/2)
    for k in range(3,100000,2):
        if round(remain%k)==0:
             fac.append(k)
             while round(remain%k)==0:
                 remain=round(remain/k)
    if remain>1.5:
        fac.append(round(remain))
    for fa in fac:
        res=round(res*(1-1/fa))
    return round(res)
        
#傻逼codeforces
if __name__=="__main__":
    T=input()
    T=int(T)
    A=[]
    M=[]
    for i in range(T):
        a1,m1=input().split()
        a1=int(a1);m1=int(m1)
        A.append(a1);M.append(m1)
    for i in range(T):
        a=A[i]
        m=M[i]
        d=gcd(a,m)
        b=round(m/d)
        print(fi(b))