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 sys,math,itertools
from collections import Counter,deque,defaultdict
from bisect import bisect_left,bisect_right 
from heapq import heappop,heappush,heapify
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

#素因数分解
def prime_factorize(n):
    if n == 1:
        return [1]
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

for _ in range(inp()):
    a,m = inpl()
    G = math.gcd(a,m)
    cnt = Counter(prime_factorize(m))
    cnta = Counter(prime_factorize(G))
    def lcm(a,b): return a*b//math.gcd(a,b)
    p = []
    for k,v in cnt.items():
        if cnta[k] > 0: 
            if cnta[k] == v: continue
            num = pow(k,cnta[k]+1)
        else: num = k
        p.append(lcm(G,num))
    ln = len(p)
    def cal(X):
        su = X//G
        for i in range(1,ln+1):
            for pt in itertools.combinations(p,i):
                now = 1
                for x in pt: now = lcm(now,x)
                if i%2: su -= X//now
                else: su += X//now
        return su
    print(cal(a+m-1)-cal(a-1))