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.
from math import gcd
from sys import stdin
from itertools import combinations

# count multiples of k from 1..n (both inclusive)
# k >= 1, n >= 1
def count_multiples(k, n):
    return (n - n % k) // k

# count how many numbers from 1..n (both inclusive)
# are a multiple of at least one of the prime numbers
# given in primes
def count_prime_multiples(n, primes):
    c = 0
    for i in range(1, len(primes) + 1):
        for subset in combinations(primes, i):
            product = 1
            for p in subset:
                product *= p
            multiples = count_multiples(product, n)
            # ~ print(product, multiples)
            if i % 2 == 0:
                c -= multiples
            else:
                c += multiples
    return c

# find the set of all prime numbers that divide n
def prime_factors(n):
    primes = set()
    k = 2
    rem = n
    while k*k <= n:
        while rem % k == 0:
            primes.add(k)
            rem //= k
        k += 1
    if rem > 1:
        primes.add(rem)
    return primes

# count how many numbers a from 1..n (both inclusive)
# have gcd(a, k) == 1
# naive algorithm, computes gcd for every a 
def coprime_upto_naive(n, k):
    c = 0
    for a in range(1, n + 1):
        if gcd(a, k) == 1:
            c += 1
    return c

# count how many numbers a from 1..n (both inclusive)
# have gcd(a, k) == 1
# fast algorithm, counts how many a are multiples of 
# at least one prime factor of k
def coprime_upto_fast(n, k):
    primes = prime_factors(k)
    multiples = count_prime_multiples(n, primes)
    return n - multiples


n = int(input())
for i in range(n):
    a, m = map(int, input().split())
    g = gcd(a, m)
    lower_limit = (a // g) - 1
    upper_limit = ((a + m) // g) - 1
    k = m // g
    print(coprime_upto_fast(upper_limit, k) - coprime_upto_fast(lower_limit, k))
