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.
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from itertools import combinations
import math
def primeFactorization(n):
    b=int(math.sqrt(n))
    lis=[]
    c=0
    while n%2==0:
        n=n//2
        c+=1
    if c>0:
        lis.append(2)
    if n>2:
        for i in range(3,b+2):
            c=0
            while n%i==0:
                n=n//i
                c+=1
            if c>0:
                lis.append(i)
    if n>2:
        lis.append(n)
    return lis
def solve(lis,arr,k,z):
    ans=z
    for i in range(k):
        ans*=arr[lis[i]]
    return ans
def answer(val,l,p):
    rem=l%val
    l+=(val-rem)
    rem1=p%val
    p-=rem1
    if l<=p:
        num=1
        num+=((p-l)//val)
        return num
    return 0
t=int(input())
for i in range(t):
    a,m=list(map(int,input().split()))
    z=math.gcd(a,m)
    arr=primeFactorization(m//z)
    ind=[]
    x=len(arr)
    for i in range(x):
        ind.append(i)
    l=a
    r=a+m-1
    p=r
    rem=p%z
    p-=rem
    ans=1
    ans+=((p-l)//z)
    for i in range(1,x+1):
        lis=combinations(ind,i)
        for j in lis:
            value=solve(j,arr,i,z)
            temp=answer(value,l,r)
            if i%2==0:
                ans+=temp
            else:
                ans-=temp
    print(ans)