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
from collections import Counter


def primeFactors(n):
    # Returns a counter of prime factors of n
    # e.g., 12 returns {2: 2, 3: 1}
    assert n >= 1
    factors = Counter()
    while n % 2 == 0:
        factors[2] += 1
        n //= 2
    x = 3
    while x * x <= n:
        while n % x == 0:
            factors[x] += 1
            n //= x
        x += 2
    if n != 1:
        factors[n] += 1
    return factors


def primePowPhi(p, k):
    # Returns phi(p**k)
    if k == 0:
        return 1
    return (p ** (k - 1)) * (p - 1)


def phi(n):
    # Phi is euler totient function which counts the positive integers up to a given integer n that are relatively prime to n
    ret = 1
    for p, k in primeFactors(n).items():
        ret *= primePowPhi(p, k)
    return ret


def solve(a, m):
    g = math.gcd(a, m)
    A = a // g
    M = m // g

    if False:
        # Want to find all x such that 0 < x < m and gcd(a, m) == gcd(a + x, m)
        # Bruteforce all x to check
        ans = set()
        for x in range(m):
            if math.gcd(a, m) == math.gcd(a + x, m):
                ans.add(x)

        # Define K from x such that:
        #
        #   g * K = a + x
        #         = g * A + x
        #
        # Since g * M == m, subtracting we get
        #
        #   g * (A + M - K) = m - x
        #
        # From 0 < x and x < m, we know
        #   0 < (m - x)
        #       (m - x) < m
        #
        # Since x and K are 1-to-1 this gives us a bound of what K we need to search.
        # Specifically when K = A then x = 0 and when K = M + A then x = m.
        # So count all K which are relatively prime with M in [A, A + M)
        ans2 = set()
        for K in range(A, A + M):
            if math.gcd(K, M) == 1:
                x = g * (K - A)
                ans2.add(x)
        assert ans == ans2

        # Note A and M are relatively prime.
        # So this is the same as counting all relatively prime in [0, M)
        assert phi(M) == len(ans)

    return phi(M)


if __name__ == "__main__":
    T = int(input())
    for t in range(T):
        a, m = [int(x) for x in input().split()]
        ans = solve(a, m)
        print(ans)
