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

def ex1295D():
    T = int(input())
    out = [0]*T
    for i in range(T):
        [a, m] = [int(i) for i in input().split()]
        out[i] = str(n_same_GCD(a, m))
    print("\n".join(out))

        
def computeGCD(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
   
def n_same_GCD(a, m):
    gcd = computeGCD(a, m)
    y = m//gcd # n of possible multiples
    n_mult_primes_y = n_mult_primes(y)
    return y - n_mult_primes_y
    
def n_mult_primes(y):
    ''' it return the number of values in range [0:y) that are multiples of prime divisors of y'''
    primes = primeFactors(y)
    mult_primes = 0   # n of possible values in range y that are multiple of primes
    for i in range(len(primes)):
        mult_primes += ((-1)**i)*compute_mult(y, primes, 0, i+1)
    return mult_primes
    
def compute_mult(y, divs, i, n_divs):
    n_mult = 0
    if n_divs == 0:
        return y
    for j in range(i, len(divs)-n_divs+1):
        n_mult += compute_mult(y//divs[j], divs, j+1, n_divs-1)
    return n_mult

def primeFactors(n): 
    
    pr = set()
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        pr.add(2) 
        n = n // 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            pr.add(i) 
            n = n // i 
              
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        pr.add(n)
    
    return list(pr) 

ex1295D()
