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.
#######################################################################################################################
#   Author:     BlackFyre
#   Language:   PyPy 3.7
#######################################################################################################################
 
from sys import stdin, stdout, setrecursionlimit
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log, log2
from random import seed, randint
from datetime import datetime
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd
mod = pow(10, 9) + 7
mod2 = 998244353
# setrecursionlimit(3000)
 
def inp(): return stdin.readline().strip()
def iinp(): return int(inp())
def out(var, end="\n"): stdout.write(str(var) + "\n")
def outa(*var, end="\n"): stdout.write(' '.join(map(str, var)) + end)
def lmp(): return list(mp())
def mp(): return map(int, inp().split())
def smp(): return map(str, inp().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(m, val) for j in range(n)]
def remadd(x, y): return 1 if x % y else 0
def ceil(a, b): return (a + b - 1) // b
def def_value(): return 0
def def_inf(): return inf
def atoi(s): return ord(s)-ord('a')
def inc(s, n=1): return chr((ord(s)-ord('a')+n)%26+ord('a'))

class XY:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
def rotate(a,b,c):
    ang = (b.y-a.y)*(c.x-b.x) - (b.x-a.x)*(c.y-b.y)
    if ang == 0: return 0   #0coll, +-clock, --aclock
    else: return ang/abs(ang)
    
def totient(n):
    res = n
    p = 2
    while(p * p <= n):
        if n%p==0:
            while (n%p==0):
                n = n//p;
            res -= res//p;
        p += 1;
    if (n > 1):
        res -= res//n;
    return res;
    
for _ in range(iinp()):
    a,m = mp()
    gd = gcd(a,m)
    mm = m//gd
    print(totient(mm))