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 math


def factorize(n):
    count = 0
    res=[]
    while ((n % 2 > 0) == False):
        n >>= 1
        count += 1

    if (count > 0):
        res.append(2)

    for i in range(3, int(math.sqrt(n)) + 1):
        count = 0
        while (n % i == 0):
            count += 1
            n = int(n / i)
        if (count > 0):
            res.append(i)
        i += 2


    if (n > 2):
        res.append(n)
    return res
t=int(input())
for i in range(t):
    a,m=map(int,input().split())
    g=math.gcd(a,m)
    p=a//g
    q=m//g
    div=factorize(q)
    div.sort(reverse=True)
    b=[]
    j=0
    pr=1
    while(j<len(div)):
        b.append(pr*div[j])
        pr*=b[j]
        j+=1

    pr=1
    j=0
    while(j<len(div)):
        pr*=div[j]
        j+=1
    j=1
    div=[]
    while(j<=math.sqrt(pr)):
        if pr%j==0:
            div.append(j)
            div.append(pr//j)
        j+=1
    div=sorted(list(set(div)))
    div.pop(0)
    j=0
    res1=0
    res2=0
    curr=0
    while(j<len(div)):
        z=len(factorize(div[j]))
        if z%2==1:
            res1+=math.floor((p+q-1)/div[j])
            res2+=math.floor((p-1)/div[j])
        else:
            res1 -= math.floor((p + q - 1) / div[j])
            res2 -= math.floor((p - 1) / div[j])

        j+=1


    print(q-(res1-res2))























