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 *

mod=1000000007

def binpow(a,b):
    global mod
    if b==1:
        return a%mod
    u=binpow(a,b//2)
    if b%2==0:
        return (u*u)%mod
    else:
        return (u*u*a)%mod

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

def phi(n) :

    result = n   # Initialize result as n

    # Consider all prime factors
    # of n and for every prime
    # factor p, multiply result with (1 - 1 / p)
    p = 2
    while(p * p<= n) :

        # Check if p is a prime factor.
        if (n % p == 0) :

            # If yes, then update n and result
            while (n % p == 0) :
                n = n // p
            result = result * (1.0 - (1.0 / (float) (p)))
        p = p + 1


    # If n has a prime factor
    # greater than sqrt(n)
    # (There can be at-most one
    # such prime factor)
    if (n > 1) :
        result = result * (1.0 - (1.0 / (float)(n)))

    return (int)(result)


dic={}

def ncr(n,r):
    if r>n-r:
        r=n-r
    if r==0 and n==0:
        return 1
    if r>n:
        return 0
    if n==r or r==0:
        return 1
    if r==1:
        return n
    key=str(n)+'|'+str(r)
    if key not in dic:
        dic[key]=ncr(n-1,r-1)+ncr(n-1,r)
    return dic[key]


for _ in range(int(input())):
    a,m=[int(i) for i in input().split()]
    m_=m/gcd(a,m)
    print(phi(m_))
