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.

def Same_GCDs(a, m):
    d = MCD(a, m) 
 
    return Phi(m // d)


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


def Descomp_En_Primos(n): 
    factPrimos = []

    if n % 2 == 0: 
        exp = 0

        while n % 2 == 0:
            n //= 2 
            exp += 1 
        
        factPrimos.append((2, exp))

    for i in range(3, n + 1, 2): 

        # if Es_Primo(n):
        #     factPrimos.append((n, 1))
        #     break

        if i * i > n: 
            factPrimos.append((n, 1))
            break

        if n % i == 0: # and Es_Primo(i):
            exp = 0

            while n % i == 0:
                n //= i
                exp += 1 
            
            factPrimos.append((i, exp))

            if n == 1:
                break  
        
    return factPrimos


def Es_Primo(n): 
    if n == 2:
        return True

    for i in range(2, int(n ** 1/2) + 1): 
        if n % i == 0:
            return False
    
    return True

def Phi(n):
    factores_primos = Descomp_En_Primos(n)
    
    phi = n

    for i in range(0, len(factores_primos)):
        phi = phi - phi // factores_primos[i][0] 
    return phi


t = int(input())

while t > 0:
    _input = [int(x) for x in input().split()]

    a = _input[0]
    m = _input[1]

    print(Same_GCDs(a, m))

    t -= 1
