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.
T = int(input())
 
def gen_prime(n):
    primes = []
    factor = [0] * n
    for i in range(2, n):
        if factor[i] == 0:
            factor[i] = i
            primes.append(i)
        for j in primes:
            if j * i >= n: break
            factor[j * i] = j
            if i % j == 0: break
    return primes
 
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
 
def prime_factorize(a, primes):
    m_primes = []
    for p in primes:
        if a % p == 0:
            m_primes.append(p)
            while a % p == 0:
                a //= p
    if a > 1:
        m_primes.append(a)
    return m_primes
 
def count_coprime(m, n_primes):
    k = len(n_primes)
    s = 0
    for i in range(1 << k):
        z = 1
        y = 0
        for j in range(k):
            if ((1 << j) & i) != 0:
                z *= n_primes[j]
                y += 1
        if y % 2 == 1:
            s -= m // z
        else:
            s += m // z
    return s
 
primes = gen_prime(100010)
 
for _ in range(T):
    n, m = list(map(int, input().split()))
    g = gcd(n, m)
    a = n // g
    b = m // g
    r = count_coprime(a + b - 1, prime_factorize(b, primes))
    s = count_coprime(a - 1, prime_factorize(b, primes))
    print(r - s)