You are given two integers $a$ and $m$. Calculate the number of integers $x$ such that $0 \le 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 \le T \le 50$) — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains two integers $a$ and $m$ ($1 \le a < m \le 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$.

Difficulty: interview

Starter code:

Solutions:
from math import gcd

def Fenjie(n):
    k = {}
    if (n == 1):
        return {}
    a = 2
    while (n >= 2):
        if (a*a > n):
            if (n in k):
                k[n] += 1
            else:
                k[n] = 1
            break
        b = n%a
        if (b == 0):
            if (a in k):
                k[a] += 1
            else:
                k[a] = 1
            n = n//a
        else:
            a += 1
    return k

def Euler(n):
    if (n == 1):
        return 1
    k = Fenjie(n)
    m = n
    for i in k:
        m = m // i * (i-1)
    return m

t = int(input())
for _ in range(t):
    a, b = list(map(int, input().split()))
    b = b//gcd(a,b)
    print(Euler(b))


import math
def okay(n):
    ans=n
    i=2
    while i*i<=n:
        if n%i==0:
            while n%i==0:
                n=int(n/i)
            ans-=int(ans/i)
        i+=1
    if n>1:
        ans-=int(ans/n)
    return ans
t=int(input())
while t:
    t-=1
    a,m=list(map(int,input().split()))
    print(okay(int(m/math.gcd(a,m))))
            


from math import gcd

def factor(x):
	factors = set()

	f = 2

	while f * f <= x:
		while x % f == 0:
			factors.add(f)
			x //= f

		f += 1

	if x > 1:
		factors.add(x)

	return factors

for _ in range(int(input())):
	a, m = map(int, input().split())

	g = gcd(a, m)

	a //= g
	m //= g

	# now just find such that 0 <= x < m & gcd(a + x, m) = 1
	# how many numbers in [a, a + m) are coprime to m

	f = list(factor(m))

	tot = 0

	for i in range(1, 2 ** len(f)):
		mul = 1

		bc = -1

		for j in range(len(f)):
			if i & (1 << j):
				mul *= f[j]
				bc = -bc

		tot += bc * (m // mul + (a % mul < (a + m - 1) % mul))

	print(m - tot)

primes=[True]*1000001
primes[0]=False
primes[1]=False
for i in range(2, 100001):
    if primes[i]:
        for j in range(i*2, 100001, i):
            primes[j]=False
pL=[]
for i in range(2, 100001):
    if primes[i]:pL.append(i)
def fact(n):
    L=[]
    for i in pL:
        if n%i==0:
            while n%i==0:
                L.append(i)
                n//=i
    if n!=1:L.append(n)
    return L
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
for i in ' '*int(input()):
    a,m=map(int,input().split())
    g=gcd(a,m)
    aa=a//g
    mm=m//g
    L=fact(mm)
    M=[]
    for i in L:
        if i not in M:M.append(i)
    for i in M:
        mm*=(i-1)
        mm//=i
    print(mm)

from math import gcd
t = int(input())


for _ in range(t):
    a, m = map(int, input().split())

    b = m//gcd(a, m)

    p = set()
    pow = {}

    i = 2
    while (i*i<=b):
        while (b%i==0):
            if i not in p:
                p.add(i)
                pow[i] = 0
            pow[i]+=1
            b//=i
        i+=1
    if (b>1):
        p.add(b)
        pow[b] = 1

    ans = 1
    for prost in p:
        ans*=prost**(pow[prost]-1)*(prost-1)
    print(ans)

from math import gcd

def popcnt(n):
	return bin(n).count("1") % 2

def calc(gen, limit):
	divisors = []
	i = 2
	gen_copy = gen
	while gen > 1 and i*i <= gen_copy:
		if gen%i == 0:
			divisors.append(i)
			while gen%i == 0:
				gen //= i
		i += 1
	if gen != 1:
		divisors.append(gen)
	#print(divisors)

	l = len(divisors)
	res = 0
	for bit in range(1 << l):
		prod = 1
		for j, div in enumerate(divisors):
			if (bit>>j) & 1:
				prod *= div
		#print(bit, prod)
		if popcnt(bit):
			res -= (limit-1) // prod
		else:
			res += (limit-1) // prod
	return res



T = int(input())
for _ in range(T):
	a, m = map(int, input().split())
	g = gcd(a, m)
	k, l = a//g, m//g
	print(calc(l, l+k) - calc(l, k))

from math import gcd


def solve(n):
    ans = n
    i = 2
    while i ** 2 <= n:
        if not n % i:
            while not n % i:
                n //= i
            ans -= ans // i
        i += 1
    if n > 1:
        ans -= ans // n
    return ans


def main():
    for _ in range(int(input())):
        a, m = list(map(int, input().split()))
        a = gcd(a, m)
        n = m // gcd(a, m)
        print(solve(m // gcd(a, m)))


main()


from functools import *
from math import gcd
from collections import *
def isValid(n):
    if n <= 0: return 0
    if n - int(n) != 0: return 0
    return 1
def mu(n):
    if n == 1:
        return 1
    elif isDivisibleBySquare(n):
        return 0
    else:
        return (-1) ** numberOfFactors(n)
def isDivisibleBySquare(n):
    if n % 2 == 0:
        n = n / 2
    if n % 2 == 0:
        return True
    for i in range(3, int(n ** 0.5) + 1):
        if n % i == 0:
            n //= i
        if n % i == 0:
            return True
    return False
def factorGenerator(n):
    r = []
    while n % 2 == 0:
        n //= 2
        r.append(2)
    i = 3
    while i * i <= n:
        while n % i == 0:
            n //= i
            r.append(i)
        i += 2
    if n != 1:
        r.append(n)
    return r
def numberOfFactors(n):
    return len(factorGenerator(n))
def divisors(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def calc(m, n):
    # Calculate number of integers in [1, m] coprime to n
    s = 0
    for d in sorted(list(set(divisors(n)))):
        s += mu(d) * (m // d)
    return s

n = int(input())
for _ in range(n):
    a, m = list(map(int, input().split()))
    g = gcd(a, m)
    # print (calc(a, m))
    print(calc((m + a - 1) // g, m // g) - calc((a - 1) // g, m // g))
    # print (sum(gcd(a, m) == gcd(a + x, m) for x in range(m)))