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 sys
from collections import Counter
readline = sys.stdin.readline

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

def prsh(N):
    prime = [2]
    for L in range(3,N):
        for p in prime:
            if not L % p:
                break
            if p > L**(1/2):
                prime.append(L)
                break
    return prime

primes = prsh(222222)
def munum(N):
    C = Counter()
    diviprimes = []
    cnt = 0
    p = 0
    while N >= p**2:
        p = primes[cnt]
        if N % p == 0:
            diviprimes.append(p)
            N //= p
            while N % p == 0:
                N //= p
        cnt += 1
    if N != 1:
        diviprimes.append(N)
    M = len(diviprimes)
    for i in range(1<<M):
        res = 1
        k = popcount(i)
        for j in range(M):
            if i&(1<<j):
                res *= diviprimes[j]
        C[res] = (-1)**k
    
    return C

def calc(x, l):
    L = munum(l)
    res = 0
    for k, v in L.items():
        res += v*(x//k)
    return res
    
    
Qu = int(readline())
Ans = [None]*Qu

for qu in range(Qu):
    a, m = map(int, readline().split())
    d = gcd(a, m)
    k1 = a//d - 1
    k2 = (a+m-1)//d
    
    l = m//d
    Ans[qu] = calc(k2, l) - calc(k1, l)
print('\n'.join(map(str, Ans)))