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: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
t = int(input())

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


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)
	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
		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))


import sys
input = sys.stdin.readline
import math
from fractions import gcd

def prime(n):
	factor = {}
	tmp = int(math.sqrt(n)) + 1
	for num in range(2, tmp):
		while n % num == 0:
			n //= num
			if not num in factor.keys():
				factor[num] = 1
			else:
				factor[num] += 1
		if num > n:
			break
	if n != 1:
		if not n in factor.keys():
			factor[n] = 1
		else:
			factor[n] += 1
	return factor
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]
for (a, m) in Query:
	g = gcd(a, m)
	m //= g
	primes = prime(m)
	p = m
	for n in primes.keys():
		p = p // n * (n - 1)
	print(p)


import math

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


import math

def gcd(a, b):
	while 1:
		b = b % a
		if b == 0:
			return a
		a = a % b
		if a == 0:
			return b
t = int(input())
for i2 in range(t):
	(a, m) = map(int, input().split())
	k = gcd(a, m)
	ans = m // k
	x = m // k
	i = 1
	for i in range(2, math.ceil(x ** (1 / 2)) + 1):
		if x % i == 0:
			while x % i == 0:
				x //= i
			ans -= ans // i
	if x >= 2:
		ans -= ans // x
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def SOE(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	pp = []
	for p in range(n + 1):
		if prime[p]:
			pp.append(p)
	return pp
primes = SOE(10 ** 5 + 10)
import math
from bisect import bisect_left as bsl
for j in range(int(input())):
	(a, m) = map(int, input().split())
	ans = gcd(a, m)
	temp = m // ans
	ind = min(bsl(primes, math.ceil(math.ceil(temp))) + 1, len(primes) - 1)
	divs = []
	for s in range(ind + 1):
		if temp % primes[s] == 0:
			divs.append(primes[s])
			while temp % primes[s] == 0:
				temp = temp // primes[s]
	if temp > 1:
		divs.append(temp)
	sub = m // ans
	for div in divs:
		sub = sub // div
		sub *= div - 1
	print(sub)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def SI():
	return sys.stdin.readline()[:-1]

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def MF():
	return map(float, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LF():
	return list(map(float, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def PrimeFactorization(x):

	def plist(x):
		if x < 2:
			return []
		if x & 1 == 0:
			return [2] + plist(x // 2)
		for p in range(3, x + 1, 2):
			if x % p == 0:
				return [p] + plist(x // p)
			if p ** 2 > x:
				return [x]
	pl = plist(x)
	(pp, ee) = ([], [])
	for p in pl:
		if not pp or p != pp[-1]:
			pp += [p]
			ee += [0]
		ee[-1] += 1
	return pp

def NumberOfRelativelyPrime(pp, a):
	res = 0
	pn = len(pp)
	for bit in range(1 << pn):
		d = 1
		for i in range(pn):
			if bit >> i & 1:
				d *= pp[i]
		if bin(bit).count('1') % 2:
			res -= a // d
		else:
			res += a // d
	return res

def main():
	t = II()
	for _ in range(t):
		(a, m) = MI()
		g = gcd(a, m)
		(a, m) = (a // g, m // g)
		pp = PrimeFactorization(m)
		ans = NumberOfRelativelyPrime(pp, m + a - 1) - NumberOfRelativelyPrime(pp, a - 1)
		print(ans)
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):
	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) = map(int, input().split())
	g = gcd(a, m)
	print(calc((m + a - 1) // g, m // g) - calc((a - 1) // g, m // g))


from math import gcd

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def solve(a, m):
	k = gcd(a, m)
	return phi(m // k)
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	print(solve(a, m))


def mcd(a, b):
	while b != 0:
		c = a % b
		a = b
		b = c
	return a

def primeFactors(n):
	factores = []
	if n % 2 == 0:
		exp = 0
		while n % 2 == 0:
			exp += 1
			n //= 2
		factores.append((2, exp))
	i = 3
	while i * i <= n:
		if n % i == 0:
			exp = 0
			while n % i == 0:
				exp += 1
				n //= i
			factores.append((i, exp))
		i += 2
	if n > 2:
		factores.append((n, 1))
	return factores

def Phi(n):
	phi = 1
	for fact in primeFactors(n):
		phi *= fact[0] ** (fact[1] - 1) * (fact[0] - 1)
	return phi
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	print(Phi(m // mcd(a, m)))


from math import gcd
from itertools import combinations

def main():
	T = int(input().strip())
	for _ in range(T):
		(a, m) = [int(s) for s in input().strip().split()]
		d = gcd(a, m)
		a //= d
		m //= d
		factors = set()
		tmp = m
		while tmp % 2 == 0:
			factors.add(2)
			tmp //= 2
		i = 3
		while i ** 2 <= tmp:
			while tmp % i == 0:
				factors.add(i)
				tmp //= i
			i += 2
		if tmp > 1:
			factors.add(tmp)
		result = 0
		for i in range(len(factors) + 1):
			for t in combinations(factors, i):
				d = 1
				for j in t:
					d *= j
				result += (-1) ** i * ((a + m - 1) // d - (a - 1) // d)
		print(result)
main()


t = int(input())

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

def euler(m):
	x = 2
	res = 1
	mi = m
	while x * x <= mi:
		cnt = 0
		while mi % x == 0:
			mi = mi // x
			cnt += 1
		if cnt > 0:
			res = res * (x ** cnt - x ** (cnt - 1))
		x += 1
	if mi == 1:
		return res
	return res * (mi - 1)

def total(a, m):
	d = gcd(a, m)
	if d == 1:
		return euler(m)
	if d > 1:
		return total(a // d, m // d)
for _ in range(t):
	(a, m) = list(map(int, input().split()))
	print(total(a, m))


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

def getPrimeFactors(n):
	factorSet = set()
	factor = 2
	while factor * factor <= n:
		while n % factor == 0:
			factorSet.add(factor)
			n //= factor
		factor += 1
	if n > 1:
		factorSet.add(n)
	return factorSet

def calculateTotient(n):
	for p in getPrimeFactors(n):
		n *= p - 1
		n //= p
	return n
n = int(input())
for _ in range(n):
	(a, m) = [int(i) for i in input().split()]
	print(calculateTotient(m // gcd(a, m)))


import math
ts = int(input())
for case in range(ts):
	(a, b) = map(int, input().split())
	gc = math.gcd(a, b)
	koto = (b - 1) // gc
	baki = b // gc
	gc_lis = []
	for i in range(2, int(math.sqrt(baki)) + 1):
		if baki % i == 0:
			gc_lis.append(i)
			while baki % i == 0:
				baki //= i
	if baki > 1:
		gc_lis.append(baki)
	total = koto
	for j in range(1, 1 << len(gc_lis)):
		mul = 1
		cnt = 0
		for k in range(0, len(gc_lis)):
			if j & 1 << k != 0:
				mul *= gc_lis[k]
				cnt += 1
		if cnt % 2 == 1:
			total -= koto // mul
		else:
			total += koto // mul
	print(total)


import sys, math
for ii in range(int(input())):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	m = int(m / g)
	ans = m
	for i in range(2, int(math.sqrt(m)) + 1):
		if m % i == 0:
			ans -= ans / i
		while m % i == 0:
			m = int(m / i)
	if m > 1:
		ans -= ans / m
	print(int(ans))


from math import gcd
MAX = 10 ** 5 + 100
PRIME = [True] * MAX
for v in range(1, MAX):
	if v == 1:
		PRIME[v] = False
		continue
	if PRIME[v] == True:
		for u in range(2 * v, MAX, v):
			PRIME[u] = False
		continue

def solve():
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	m //= g
	res = m
	for p in range(2, MAX):
		if PRIME[p] == True and m % p == 0:
			res //= p
			res *= p - 1
			while m % p == 0:
				m //= p
	if m > 1:
		res //= m
		res *= m - 1
	print(res)
	return

def main():
	testcase = int(input())
	for i in range(testcase):
		solve()
	return
main()


def phi(m):
	(ans, i) = (m, 2)
	while i * i <= m:
		if m % i != 0:
			i += 1
			continue
		while m % i == 0:
			m //= i
		ans -= ans // i
		i += 1
	if m > 1:
		ans -= ans // m
	return ans
from math import gcd
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	m = m // gcd(a, m)
	print(phi(m))


from math import sqrt
primes = [2]
seen = set()
for i in range(3, int(100000.0), 2):
	if i not in seen:
		primes.append(i)
		for j in range(i + i, int(100000.0), i):
			seen.add(j)

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

def hipow(n, x):
	if n % x:
		return (1, n)
	(ret, n) = hipow(n, x * x)
	if n % x == 0:
		ret *= x
		n //= x
	return (ret, n)

def totient(n):
	ret = 1
	lim = sqrt(n)
	for d in primes:
		if n % d == 0:
			(t, n) = hipow(n, d)
			ret *= t - t // d
		if n == 1:
			break
	else:
		ret *= n - 1
	return ret
T = int(input().strip())
for _ in range(T):
	(a, m) = map(int, input().split())
	d = gcd(a, m)
	print(totient(m // d))


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	result += 0.1
	return int(result)

def solve(a, m):
	g = gcd(a, m)
	mPrime = m // g
	return phi(mPrime)
t = int(input())
for _ in range(t):
	(a, m) = [int(x) for x in input().split()]
	print(solve(a, m))


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))


from math import gcd

def prime_decomposition(n):
	i = 2
	table = dict()
	while i * i <= n:
		c = 0
		while n % i == 0:
			n /= i
			c += 1
		if c != 0:
			table[i] = c
		i += 1
	if n > 1:
		table[int(n)] = 1
	return table

def f(N, ps):
	M = len(ps)
	r = 0
	for i in range(2 ** M):
		(t, l) = (0, 1)
		for j in range(M):
			if i % 2:
				l *= ps[j]
				t += 1
			i = i >> 1
		r += (-1 if t % 2 else 1) * (N // l)
	return r
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	aa = prime_decomposition(a)
	mm = prime_decomposition(m)
	ps = list()
	g = gcd(a, m)
	for key in mm:
		if key in aa and aa[key] >= mm[key]:
			continue
		ps.append(key)
	print(f(m // g - 1, ps))


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	k = m // gcd(a, m)
	phi = k
	i = 2
	while i * i <= k:
		if k % i == 0:
			while k % i == 0:
				k //= i
			phi -= phi // i
		i += 1
	if k > 1:
		phi -= phi // k
	print(phi)


from math import sqrt, gcd

def factors(x):
	t = sqrt(x)
	s = set()
	i = 2
	while x > 1 and i <= t:
		if x % i == 0:
			s.add(i)
			x = x // i
		else:
			i += 1
	if x > 1:
		s.add(x)
	return list(s)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	b = b // gcd(a, b)
	l = factors(b)
	for i in l:
		b = b * (i - 1)
		b = b // i
	print(b)


import math

def phi(x):
	i = 2
	ans = x
	while i * i <= x:
		cnt = 0
		while x % i == 0:
			x //= i
			cnt += 1
		if cnt > 0:
			ans -= ans // i
		i += 1
	if x > 1:
		ans -= ans // x
	return ans

def solve():
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	ans = 0
	a //= g
	m //= g
	print(phi(m))
for tt in range(int(input())):
	solve()


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

def phi(m):
	res = m
	for i in range(2, int(m ** 0.5) + 1):
		if m % i == 0:
			while m % i == 0:
				m = m // i
			res -= res // i
	if m > 1:
		res -= res // m
	return res
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	m = m // g
	print(phi(m))


def phi(n):
	l = []
	i = 2
	pro = n
	while i * i <= n:
		if n % i == 0:
			l.append(i)
			while n % i == 0:
				n = n // i
		i += 1
	if n != 1:
		l.append(n)
	for i in l:
		pro = pro // i * (i - 1)
	return pro

def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
t = int(input())
for you in range(t):
	l = input().split()
	a = int(l[0])
	m = int(l[1])
	k = m // gcd(a, m)
	print(phi(k))


import math
t = int(input())

def gcd(a, b):
	mn = min(a, b)
	mx = max(a, b)
	if mx % mn == 0:
		return mn
	else:
		return gcd(mx % mn, mn)
for i in range(t):
	(a, m) = map(int, input().strip().split())
	g = gcd(a, m)
	m = m / g
	n = m
	primeFactors = {}
	if m == 1:
		print(1)
	else:
		highest = math.floor(math.sqrt(m))
		for i in range(2, highest + 1):
			while m % i == 0:
				primeFactors[i] = True
				m = m / i
		if m != 1:
			primeFactors[m] = True
		for key in primeFactors.keys():
			n = n * (key - 1) / key
		if len(primeFactors.keys()) == 0:
			print(int(n - 1))
		else:
			print(int(n))


T = int(input())
Ans = []
for i in range(T):
	(a, m) = map(int, input().split())
	gcd = m
	while a != 0:
		(gcd, a) = (a, gcd % a)
	m //= gcd
	temp_1 = m
	temp_2 = 2
	res = m
	while temp_2 * temp_2 <= m:
		if temp_1 % temp_2 == 0:
			res *= temp_2 - 1
			res //= temp_2
			while temp_1 % temp_2 == 0:
				temp_1 //= temp_2
		temp_2 += 1
	if temp_1 > 1:
		res *= temp_1 - 1
		res //= temp_1
	Ans.append(res)
for k in Ans:
	print(k)


import sys
input = sys.stdin.readline
from math import gcd
from itertools import combinations as cc
t = int(input())

def rec(ind, prod, co=0):
	global tot
	if ind == len(fac):
		if prod == 1:
			return
		if co % 2 == 1:
			tot += r // prod - (l - 1) // prod
		else:
			tot -= r // prod - (l - 1) // prod
	else:
		rec(ind + 1, prod, co)
		rec(ind + 1, prod * fac[ind], co + 1)
for _ in range(t):
	(a, m) = map(int, input().split())
	tot = 0
	x = gcd(a, m)
	m //= x
	a //= x
	l = a
	r = a + m - 1
	fac = []
	for i in range(1, int(m ** 0.5) + 2):
		if m % i == 0:
			if i != 1:
				st = 1
				for j in range(2, min(int(i ** 0.5) + 2, i)):
					if i % j == 0:
						st = 2
						break
				if st == 1:
					fac.append(i)
			i = m // i
			if i != 1:
				st = 1
				for j in range(2, min(int(i ** 0.5) + 2, i)):
					if i % j == 0:
						st = 2
						break
				if st == 1:
					fac.append(i)
	fac = list(set(fac))
	rec(0, 1, 0)
	print(m - tot)


from math import *
from bisect import *

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = int(n / p)
			result -= int(result / p)
		p += 1
	if n > 1:
		result -= int(result / n)
	return result
test = int(input())
for i in range(test):
	(a, m) = input().split()
	a = int(a)
	m = int(m)
	d = gcd(a, m)
	num = m // d
	ans = phi(num)
	print(ans)


t = int(input())
import math

def factorize(n):
	d = {}
	temp = int(math.sqrt(n)) + 1
	for i in range(2, temp):
		while n % i == 0:
			n //= i
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	if d == {}:
		d[n] = 1
	elif n in d:
		d[n] += 1
	elif n != 1:
		d[n] = 1
	return d

def euler_phi(n):
	res = n
	d = factorize(n)
	for (p, _) in d.items():
		if p == 1:
			continue
		res = res // p * (p - 1)
	return res
for _ in range(t):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	ans = euler_phi(m // g)
	print(ans)


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7

def phi(n):
	ans = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			ans //= i
			ans *= i - 1
			while not n % i:
				n //= i
		i += 1
	if n > 1:
		ans //= n
		ans *= n - 1
	return ans
for _ in range(I()):
	(a, m) = R()
	print(phi(m // gcd(m, a)))


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = math.gcd(a, b)
	b //= s
	m = b
	l = []
	for i in range(2, int(math.sqrt(b)) + 1):
		if b % i == 0:
			l.append(i)
			while b % i == 0:
				b //= i
	if b > 1:
		l.append(b)
	for i in range(len(l)):
		m *= l[i] - 1
		m //= l[i]
	print(m)


import sys
input = sys.stdin.readline
import math
t = int(input())
for test in range(t):
	(a, m) = map(int, input().split())
	GCD = math.gcd(a, m)
	x = m // GCD
	L = int(math.sqrt(x))
	FACT = dict()
	for i in range(2, L + 2):
		while x % i == 0:
			FACT[i] = FACT.get(i, 0) + 1
			x = x // i
	if x != 1:
		FACT[x] = FACT.get(x, 0) + 1
	ANS = m // GCD
	for f in FACT:
		ANS = ANS * (f - 1) // f
	print(ANS)


from math import gcd

def phi(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			result = result - result // i
		while n % i == 0:
			n = n // i
		i = i + 1
	if n > 1:
		result = result - result // n
	return result
t = int(input())
for ti in range(t):
	(n, m) = map(int, input().split())
	g = gcd(n, m)
	ans = phi(m // g)
	print(ans)


from math import gcd, sqrt, ceil
isPrime = [0, 0] + [1] * 1000001
for i in range(2, 1000001):
	if isPrime[i]:
		for j in range(2 * i, 1000001, i):
			isPrime[j] = 0

def isItPrime(n):
	for i in range(2, 1 + int(sqrt(n))):
		if n % i == 0:
			return 0
	return 1
t = int(input())
while t:
	t -= 1
	(a, m) = list(map(int, input().split()))
	hcf = gcd(a, m)
	a //= hcf
	m //= hcf
	primes = []
	for i in range(1, 1 + int(sqrt(m))):
		if m % i == 0:
			if isPrime[i]:
				primes.append(i)
			if i != m // i and isItPrime(m // i):
				primes.append(m // i)
	n = len(primes)
	ans = m
	for i in range(1, 2 ** n):
		b = bin(i)[2:].rjust(n, '0')
		temp = 1
		for j in range(n):
			if b[j] == '1':
				temp *= primes[j]
		left = ceil(a / temp) * temp
		right = (a + m - 1) // temp * temp
		count = (right - left) // temp + 1
		if b.count('1') & 1:
			ans -= count
		else:
			ans += count
	print(ans)


def gcd(a, m):
	if a % m != 0:
		return gcd(m, a % m)
	else:
		return m

def phi(n):
	l = []
	p = [0] * 40
	j = 0
	i = 2
	copy = n
	flag = 1
	while n != 1:
		if i * i > n and flag == 1:
			l.append(n)
			p[len(l) - 1] = 1
			n = 1
			break
		if n % i == 0:
			if flag == 1:
				l.append(i)
				flag = 0
			n = n // i
			p[len(l) - 1] += 1
		else:
			flag = 1
			i += 1
	ans = 1
	for i in range(len(l)):
		ans = ans * (l[i] - 1) * l[i] ** (p[i] - 1)
	return ans
n = int(input())
for i in range(n):
	(a, m) = input().split()
	a = int(a)
	m = int(m)
	d = gcd(a, m)
	print(phi(m // d))


import sys
from math import gcd
from itertools import combinations
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	opt = m // g
	a //= g
	m //= g
	ps = []
	if not m & 1:
		ps.append(2)
		while not m & 1:
			m >>= 1
	limit = int(m ** 0.5) + 1
	f = 3
	while f < limit and f <= m:
		if m % f == 0:
			ps.append(f)
			while m % f == 0:
				m //= f
		f += 2
	if m > 1:
		ps.append(m)
	ctr = 0
	for w in range(1, len(ps) + 1):
		for fs in combinations(ps, w):
			prod = 1
			for f in fs:
				prod *= f
			add = (a + opt - 1) // prod - (a - 1) // prod
			if w & 1:
				ctr += add
			else:
				ctr -= add
	print(opt - ctr)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def totient(x):
	tot = x
	n = x
	i = 1
	prime_factors = []
	q = 2
	while n > 1 and q * q <= n:
		if n % q == 0:
			prime_factors.append(q)
			while n % q == 0:
				n //= q
		q += 1
	if n > 1:
		prime_factors.append(n)
	for p in prime_factors:
		tot = tot / p * (p - 1)
	return int(tot)
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	g = gcd(m, a)
	ans = 0
	count = 0
	prime_factors = []
	m1 = m // g
	ans = totient(m1)
	print(ans)


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
for testcase in range(int(input())):
	(a, m) = list((int(x) for x in input().split(' ')))
	m = m // gcd(a, m)
	res = m
	if m % 2 == 0:
		res //= 2
	while m % 2 == 0:
		m //= 2
	i = 3
	while i * i <= m:
		if m % i == 0:
			while m % i == 0:
				m //= i
			res = res // i * (i - 1)
		i += 2
	if m != 1:
		res = res // m * (m - 1)
	print(res)


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 sys
input = sys.stdin.readline

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

def prime_factor(n):
	ass = []
	for i in range(2, int(n ** 0.5) + 1):
		while n % i == 0:
			ass.append(i)
			n = n // i
	if n != 1:
		ass.append(n)
	return list(set(ass))
t = int(input())
for testcase in range(t):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	a = a // g
	m = m // g
	p = prime_factor(m)
	k = len(p)
	res = m
	for i in range(1, 1 << k):
		cp = 0
		pri = 1
		for j in range(k):
			if i >> j & 1 == 1:
				pri *= p[j]
				cp += 1
		if a % pri == 0:
			cnt = m // pri + 1
		else:
			start = (a // pri + 1) * pri
			if start > a + m - 1:
				cnt = 0
			else:
				cnt = (a + m - start) // pri + 1
		res += (-1) ** cp * cnt
	print(res)


import math
inp = int(input())

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def prm(a):
	for i in range(2, int(math.sqrt(a) + 1)):
		if a % i == 0:
			return False
	return True
for t in range(inp):
	(a, m) = map(int, input().split())
	d = math.gcd(a, m)
	big = m / d
	print(phi(big))


def gcd(x, y):
	if x == 0 or y == 0:
		return max(round(x), round(y))
	elif x > y:
		return gcd(round(x % y), round(y))
	else:
		return gcd(round(x), round(y % x))

def fi(x):
	fac = []
	remain = round(x)
	res = round(x)
	if round(remain % 2) == 0:
		fac.append(2)
		while round(remain % 2) == 0:
			remain = round(remain / 2)
	for k in range(3, 100000, 2):
		if round(remain % k) == 0:
			fac.append(k)
			while round(remain % k) == 0:
				remain = round(remain / k)
	if remain > 1.5:
		fac.append(round(remain))
	for fa in fac:
		res = round(res * (1 - 1 / fa))
	return round(res)
T = input()
T = int(T)
A = []
M = []
for i in range(T):
	(a1, m1) = input().split()
	a1 = int(a1)
	m1 = int(m1)
	A.append(a1)
	M.append(m1)
for i in range(T):
	a = A[i]
	m = M[i]
	d = gcd(a, m)
	b = round(m / d)
	print(fi(b))


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
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	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_))


from math import gcd, sqrt

def prime_factor(n):
	factors = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			factors.append(i)
			while n % i == 0:
				n //= i
	if n != 1:
		factors.append(n)
	return factors

def count_multiples(n, primes):
	n -= 1
	count = 0
	for bits in range(1, 1 << len(primes)):
		x = 1
		c = 0
		for i in range(len(primes)):
			if bits >> i & 1:
				c += 1
				x *= primes[i]
		count += n // x * (-1) ** (c + 1)
	return count
T = int(input())
for _ in range(T):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	primes = prime_factor(m // g)
	print(m // g - count_multiples((a + m) // g, primes) + count_multiples(a // g, primes))


import sys
import math
import operator as op
from functools import reduce

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom

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

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)
t = read_int()
for i in range(t):
	(a, m) = read_int_line()
	d = gcd(a, m)
	a = a // d
	m = m // d
	ans = phi(m)
	print(ans)


def GCD(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def factors(n):
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n //= p
			yield p
		else:
			p += 1
	if n > 1:
		yield n

def phi(n):
	result = n
	for p in factors(n):
		result *= p - 1
		result //= p
	return result

def solve(a, m):
	return phi(m // GCD(a, m))
T = int(input())
for i in range(T):
	print(solve(*map(int, input().split())))


import math

def sieve(n):
	prime = [-1] * (n + 1)
	for i in range(2, n + 1):
		if prime[i] == -1:
			for j in range(i, n + 1, i):
				prime[j] = i
	return prime

def totient(n):
	m = n
	primes = []
	i = 1
	while n > 1 and i < int(n ** 0.5) + 1:
		if n % i == 0 and p[i] == i:
			primes.append(i)
			while n % i == 0:
				n = n // i
		i += 1
	if n != 1:
		primes.append(n)
	if len(primes) == 0:
		return n - 1
	ans = m
	for i in primes:
		ans = ans // i
	for i in primes:
		ans = ans * (i - 1)
	return ans
p = sieve(100000)
for nt in range(int(input())):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	m1 = m // g
	print(totient(m1))


from math import gcd

def totatives(n):
	phi = int(n > 1 and n)
	for p in range(2, int(n ** 0.5) + 1):
		if not n % p:
			phi -= phi // p
			while not n % p:
				n //= p
	if n > 1:
		phi -= phi // n
	return phi
for _ in range(int(input())):
	(x, m) = map(int, input().split())
	print(totatives(m // gcd(x, m)))


import sys
input = sys.stdin.readline
import math
t = int(input())

def calc(MIN, MAX, k):
	return MAX // k - (MIN - 1) // k
for test in range(t):
	(a, m) = map(int, input().split())
	GCD = math.gcd(a, m)
	MIN = a
	MAX = a + m - 1
	x = m // GCD
	L = int(math.sqrt(x))
	FACT = dict()
	for i in range(2, L + 2):
		while x % i == 0:
			FACT[i] = FACT.get(i, 0) + 1
			x = x // i
	if x != 1:
		FACT[x] = FACT.get(x, 0) + 1
	FL = list(FACT)
	ANS = 0
	LEN = len(FACT)
	for i in range(1 << LEN):
		count = 0
		score = GCD
		for j in range(LEN):
			if i & 1 << j != 0:
				count += 1
				score *= FL[j]
		ANS += calc(MIN, MAX, score) * (-1) ** count
	print(ANS)


def gcdcalc(a, m):
	if m % a == 0:
		return a
	return gcdcalc(m % a, a)

def gcdnumber(m):
	temp = m
	ans = m
	d = 2
	cnt = 0
	while d * d <= temp:
		if temp % d == 0:
			ans = ans - ans // d
			while temp % d == 0:
				temp = temp // d
			cnt = 1
		d += 1
	if temp > 0 and temp != 1:
		ans = ans - ans // temp
	return ans
t = int(input())
l = []
for i in range(t):
	(a, m) = map(int, input().strip().split())
	gcd = gcdcalc(a, m)
	ans = gcdnumber(m // gcd)
	l.append(ans)
for i in l:
	print(i)


import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())

def GCD(x, y):
	return GCD(y, x % y) if y else x
for _ in range(int(input())):
	(a, m) = mapi()
	m //= GCD(a, m)
	res = m
	den = 1
	for i in range(2, int(m ** 0.5) + 1):
		if m % i == 0:
			while m % i == 0:
				m //= i
			res *= i - 1
			den *= i
	if m > 1:
		res *= m - 1
		den *= m
	print(res // den)


from sys import stdin, stdout
from math import gcd
input = stdin.readline

def h(x):
	res = 0
	for mask in range(1, 1 << len(p)):
		mult = 1
		for i in range(len(p)):
			if mask >> i & 1:
				mult *= p[i]
		if bin(mask).count('1') & 1:
			res += x // mult
		else:
			res -= x // mult
	return res
for _ in range(int(input())):
	global a, m, p
	p = []
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	a //= g
	m //= g
	i = 2
	cnt = 1
	t = m
	while i * i <= m:
		if not t % i:
			p.append(i)
			while not t % i:
				t //= i
		i += 1
	if t > 1:
		p.append(t)
	print(m - h(a) - h(m) + h(a - 1))


from math import gcd

def phi(n):
	m = n
	factors = set()
	q = 2
	while n > 1 and q * q <= n:
		if n % q == 0:
			factors.add(q)
			n //= q
		else:
			q += 1
	if n > 1:
		factors.add(n)
	for p in factors:
		m *= p - 1
		m //= p
	return m
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	m //= gcd(a, m)
	print(phi(m))


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

def phitrue(a):
	(tmp, ans) = (a, a)
	d = 2
	while d * d <= tmp:
		cnt = 0
		while tmp % d == 0:
			tmp /= d
			cnt += 1
		if cnt > 0:
			ans -= ans / d
		d += 1
	if tmp > 1:
		ans -= ans / tmp
	return ans
t = int(input())
ans = []
for i in range(t):
	(a, m) = map(int, input().split())
	print(round(phitrue(m / gcd(a, m))))


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) = map(int, input().split())
		a = gcd(a, m)
		n = m // gcd(a, m)
		print(solve(m // gcd(a, m)))
main()


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

def ph(a):
	i = 2
	ans = a
	while i * i <= a:
		flag = False
		while a % i == 0:
			a = a // i
			flag = True
		if flag:
			ans = ans - ans // i
		i += 1
	if a > 1:
		ans = ans - ans // a
	return ans
t = int(input())
for _ in range(t):
	(a, b) = (int(i) for i in input().split())
	print(ph(b // gcd(a, b)))


import math

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)
n = int(input())
for i in range(n):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	m = m // g
	print(phi(m))


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

def getphi(x):
	(y, i) = (1, 2)
	while i * i <= x:
		if x % i == 0:
			y *= i - 1
			x /= i
			while x % i == 0:
				y *= i
				x /= i
		i += 1
	if x > 1:
		y *= x - 1
	return y
T = int(input())
for o in range(T):
	(a, m) = map(int, input().split())
	print('%d' % getphi(m / gcd(a, m)))


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
from math import gcd
for _ in range(val()):
	(a, b) = li()
	ans = b // gcd(a, b)
	temp = ans
	i = 2
	while i * i <= temp:
		if temp % i:
			i += 1
			continue
		while not temp % i:
			temp //= i
		ans -= ans // i
		i += 1
	if temp > 1:
		ans -= ans // temp
	print(ans)


def Input():
	ans = []
	tem = input().split()
	for it in tem:
		ans.append(int(it))
	return ans

def gcd(x, y):
	if x % y == 0:
		return y
	else:
		return gcd(y, x % y)

def eular(x):
	ans = x
	i = 2
	while i * i <= x:
		if x % i == 0:
			ans -= ans // i
			while x % i == 0:
				x = x // i
		i += 1
	if x > 1:
		ans -= ans // x
	return ans
T = Input()[0]
for tt in range(T):
	(n, m) = Input()
	yue = gcd(n, m)
	(n_, m_) = (n // yue, m // yue)
	print(eular(m_))


def prime_decomposition(n):
	i = 2
	table = dict()
	while i * i <= n:
		c = 0
		while n % i == 0:
			n /= i
			c += 1
		if c != 0:
			table[i] = c
		i += 1
	if n > 1:
		table[int(n)] = 1
	return table

def f(N, mn, ds):
	M = len(ds)
	r = 0
	for i in range(1, 2 ** M):
		t = 0
		l = 1
		for j in range(M):
			if i % 2:
				l *= ds[j]
				t += 1
			i = i >> 1
		xx = (1 if t % 2 else -1) * (N // l - (mn - 1) // l)
		r += xx
	return r
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	aa = prime_decomposition(a)
	mm = prime_decomposition(m)
	ds = list()
	gcd = 1
	for key in mm:
		if key in aa:
			gcd *= key ** min(aa[key], mm[key])
			if aa[key] >= mm[key]:
				continue
		ds.append(key)
	mx = -(-(a + m) // gcd) - 1
	mn = -(-a // gcd)
	print(mx - mn - f(mx, mn, ds) + 1)


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
	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)


def main():
	import sys
	from math import gcd, sqrt
	input = sys.stdin.readline

	def f(n, d):
		return n // d

	def prime(n):
		ret = {}
		for d in range(2, int(sqrt(n)) + 1):
			while n % d == 0:
				ret[d] = 1
				n //= d
		if n > 1:
			ret[n] = 1
		return ret
	for _ in range(int(input())):
		(a, m) = map(int, input().split())
		k = gcd(a, m)
		p = a // k
		q = m // k
		ans = q
		pr = list(prime(q))
		np = len(pr)
		for i in range(1, 1 << np):
			sign = 0
			d = 1
			for j in range(np):
				if i >> j & 1:
					sign ^= 1
					d *= pr[j]
			sign = (-1) ** sign
			ans += (f(p + q - 1, d) - f(p - 1, d)) * sign
		print(ans)
main()


from math import gcd
import sys

def input():
	return sys.stdin.readline().rstrip()

def totient_phi(M):
	ans = M
	V = M
	for i in range(2, M + 1):
		if i * i > M:
			break
		if V % i == 0:
			while V % i == 0:
				V //= i
			ans = ans * (i - 1) // i
	if V > 1:
		ans = ans * (V - 1) // V
	return ans

def slv():
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	m //= g
	ans = totient_phi(m)
	print(ans)
	return

def main():
	t = int(input())
	for i in range(t):
		slv()
	return
main()


def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = int(n / p)
			result -= int(result / p)
		p += 1
	if n > 1:
		result -= int(result / n)
	return result
from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(phi(m // gcd(n, m)))


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

def phi(a):
	tmp = a
	ans = a
	d = 2
	while d * d <= tmp:
		cnt = 0
		while tmp % d == 0:
			tmp /= d
			cnt += 1
		if cnt > 0:
			ans -= ans / d
		d += 1
	if tmp > 1:
		ans -= ans / tmp
	return ans
n = int(input())
forprint = []
for i in range(n):
	(a, m) = map(int, input().split())
	forprint.append(str(int(phi(m / mcd(a, m)))))
print('\n'.join(forprint))


import math

def cal(x, y, z):
	return z // x - y // x
T = int(input())
while T:
	T -= 1
	(a, m) = map(int, input().split())
	k = math.gcd(a, m)
	x = (m - 1) // k
	n = m // k
	i = 2
	p = []
	while i * i <= m // k:
		if n % i == 0:
			while n % i == 0:
				n //= i
			p.append(i)
		i += 1
	if n > 1:
		p.append(n)
	res = 0
	for mask in range(1, 1 << len(p)):
		tmp = 1
		cnt = 0
		for i in range(len(p)):
			if mask & 1 << i:
				tmp *= p[i]
				cnt += 1
		if cnt % 2 == 1:
			res += cal(tmp, a // k, a // k + x)
		else:
			res -= cal(tmp, a // k, a // k + x)
	print(x + 1 - res)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 5)
from queue import PriorityQueue
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	g = gcd(a, b)
	m = b // g
	b //= g
	l = []
	for i in range(2, int(sqrt(m)) + 1):
		if b % i == 0:
			l.append(i)
			while b % i == 0:
				b //= i
	if b > 1:
		l.append(b)
	ans = 0
	for i in l:
		m *= i - 1
		m //= i
	print(m)


import math
import cmath
from decimal import *
from fractions import *
T = int(input())
while T > 0:
	T -= 1
	(a, m) = map(int, input().split())
	m //= math.gcd(a, m)
	ans = m
	aa = int(math.sqrt(m))
	for x in range(2, max(3, aa + 1)):
		if m <= 1:
			break
		if m % x == 0:
			while m % x == 0:
				m //= x
			ans = ans * (x - 1) // x
	if m > 1:
		ans = ans * (m - 1) // m
	print(ans)


import math

def prime_factors(n):
	assert n > 0
	if n == 1:
		return [1]
	f = []
	while n % 2 == 0:
		f.append(2)
		n /= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			f.append(i)
			n /= i
	if n > 1:
		f.append(int(n))
	return f

def factors_in(i, e, p):
	d = 0
	n = i + (p - i % p)
	while n >= i and n < e:
		d += 1
		n += p
	return d

def solve_slow():
	(a, m) = map(int, input().split())
	gcd = math.gcd(a, m)
	sol = 0
	for x in range(m):
		if gcd == math.gcd(a + x, m):
			sol += 1
	print(sol)

def eulers_phi_fun(n):
	f = prime_factors(n)
	val = n
	for i in set(f):
		val *= 1 - 1 / i
	return int(val)

def solve():
	(a, m) = map(int, input().split())
	gcd = math.gcd(a, m)
	n = m / gcd
	phi = eulers_phi_fun(n)
	print(phi)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def gcd(a, b):
	while b != 0:
		c = a % b
		a = b
		b = c
	return a

def totient(n):
	i = 2
	ret = n
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			ret = ret * (i - 1) // i
		i += 1
	if n > 1:
		ret = ret * (n - 1) // n
	return ret
tc = int(input())
for _ in range(tc):
	(a, m) = map(int, input().split())
	d = gcd(a, m)
	v = m // d
	ans = totient(v)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def toord(c):
	return ord(c) - ord('a')

def lcm(a, b):
	return a * b // lcm(a, b)
mod = 998244353
INF = float('inf')
from math import factorial, sqrt, ceil, floor, gcd
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def euler(n):
	res = n
	for i in range(2, floor(sqrt(n)) + 1):
		if n % i == 0:
			res = res * (i - 1) // i
			while n % i == 0:
				n //= i
		if n == 1:
			break
	else:
		res = res * (n - 1) // n
	return int(res)

def main():
	for _ in range(N()):
		(a, m) = RL()
		gd = gcd(a, m)
		pm = m // gd
		print(euler(pm))
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = int(n / p)
			result -= int(result / p)
		p += 1
	if n > 1:
		result -= int(result / n)
	return result

def solve():
	(a, m) = sep()
	temp = m // gcd(a, m)
	div = [temp]
	for i in range(2, floor(temp ** 0.5) + 1):
		if temp % i == 0:
			div.append(i)
			if i == temp // i:
				continue
			div.append(temp // i)
	primes = []
	for i in range(len(div)):
		if isPrime(div[i]):
			primes.append(div[i])
	ans = temp
	for i in range(len(primes)):
		ans //= primes[i]
	for i in range(len(primes)):
		ans *= primes[i] - 1
	print(ans)
testcase(int(inp()))


import os
import sys
from io import BytesIO, IOBase
import math as m

def phi(n):
	res = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			res -= res // i
		i += 1
	if n > 1:
		res -= res // n
	return res

def main():
	t = int(input())
	for tc in range(t):
		(a, b) = map(int, input().split())
		g = m.gcd(a, b)
		print(phi(b // g))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
M = 10 ** 5 + 100
prime = [True] * M
for i in range(1, M):
	if i == 1:
		prime[i] = False
	else:
		for j in range(2 * i, M, i):
			prime[j] = False
for t in range(int(input())):
	(a, b) = map(int, input().split())
	m = gcd(a, b)
	b //= m
	total = b
	for i in range(1, M):
		if prime[i] == True and b % i == 0:
			total //= i
			total *= i - 1
			while b % i == 0:
				b //= i
	if b > 1:
		total //= b
		total *= b - 1
	print(total)


from math import gcd
MX = 100000
prime = [2]

def sieve():
	mark = [True for i in range(MX)]
	for i in range(3, MX, 2):
		if mark[i]:
			prime.append(i)
			for j in range(i * i, MX, i):
				mark[j] = False

def phi(N):
	ph = N
	for p in prime:
		if N % p == 0:
			ph //= p
			ph *= p - 1
			while N % p == 0:
				N //= p
	if N > 1:
		ph //= N
		ph *= N - 1
	return ph
sieve()
T = int(input())
for cs in range(T):
	(a, m) = map(int, input().split())
	print(phi(m // gcd(a, m)))


def euler_totient(n):
	result = n
	s = int(sqrt(n))
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n //= p
			result *= 1.0 - 1.0 / float(p)
		p += 1
	if n > 1:
		result *= 1.0 - 1.0 / float(n)
	return int(result)
from math import gcd, sqrt
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	print(euler_totient(m // gcd(a, m)))


def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for T in range(t):
	(a, m) = [int(x) for x in input().split()]
	g = gcd(a, m)
	count = 0
	count = phi(m // g)
	print(count)


from math import gcd
for _ in range(int(input())):
	x = input().split(' ')
	a = int(x[0])
	m = int(x[1])
	val = gcd(a, m)
	n = m // val
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result - int(result / p)
		p = p + 1
	if n > 1:
		result = result - int(result / n)
	print(result)


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_mult_primes_y = n_mult_primes(y)
	return y - n_mult_primes_y

def n_mult_primes(y):
	primes = primeFactors(y)
	mult_primes = 0
	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()
	while n % 2 == 0:
		pr.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			pr.add(i)
			n = n // i
	if n > 2:
		pr.add(n)
	return list(pr)
ex1295D()


def R():
	return map(int, input().split())

def I():
	return int(input())

def S():
	return str(input())

def L():
	return list(R())
from collections import Counter
import math
import sys

def check(t):
	return [True, False][any((t[i] < t[i + 1] for i in range(1, len(t) - 1)))]
from itertools import permutations

def psi(n):
	n2 = n
	factors = []
	i = 1
	while i * i <= n:
		i += 1
		if n % i == 0:
			factors.append(i)
			while n % i == 0:
				n //= i
	if n > 1:
		factors.append(n)
	for p in factors:
		n2 *= p - 1
		n2 //= p
	return n2
for _ in range(I()):
	(a, m) = R()
	m //= math.gcd(a, m)
	print(psi(m))


from math import gcd

def phi(n):
	res = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res //= p
			res *= p - 1
		p += 1
	if n > 1:
		res //= n
		res *= n - 1
	return res
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	m //= g
	print(phi(m))


import os
import sys
from atexit import register
from io import StringIO
sys.stdout = StringIO()
register(lambda : os.write(1, sys.stdout.getvalue().encode()))
import math

def totient(n):
	if n == 1:
		return 1
	for k in range(2, math.ceil(math.sqrt(n) + 1)):
		if n % k == 0:
			p = 0
			while n % k == 0:
				p += 1
				n /= k
			return (k ** p - k ** (p - 1)) * totient(n)
	return n - 1
T = int(input())
for _ in range(T):
	[a, m] = [int(k) for k in input().split()]
	gcd = math.gcd(m, a)
	print(int(totient(m / gcd)))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from itertools import combinations
import math

def primeFactorization(n):
	b = int(math.sqrt(n))
	lis = []
	c = 0
	while n % 2 == 0:
		n = n // 2
		c += 1
	if c > 0:
		lis.append(2)
	if n > 2:
		for i in range(3, b + 2):
			c = 0
			while n % i == 0:
				n = n // i
				c += 1
			if c > 0:
				lis.append(i)
	if n > 2:
		lis.append(n)
	return lis

def solve(lis, arr, k, z):
	ans = z
	for i in range(k):
		ans *= arr[lis[i]]
	return ans

def answer(val, l, p):
	rem = l % val
	l += val - rem
	rem1 = p % val
	p -= rem1
	if l <= p:
		num = 1
		num += (p - l) // val
		return num
	return 0
t = int(input())
for i in range(t):
	(a, m) = list(map(int, input().split()))
	z = math.gcd(a, m)
	arr = primeFactorization(m // z)
	ind = []
	x = len(arr)
	for i in range(x):
		ind.append(i)
	l = a
	r = a + m - 1
	p = r
	rem = p % z
	p -= rem
	ans = 1
	ans += (p - l) // z
	for i in range(1, x + 1):
		lis = combinations(ind, i)
		for j in lis:
			value = solve(j, arr, i, z)
			temp = answer(value, l, r)
			if i % 2 == 0:
				ans += temp
			else:
				ans -= temp
	print(ans)


import math

def totient(x):
	i = 2
	ans = x
	while i * i <= x:
		if x % i == 0:
			ans = ans * (i - 1) // i
			while x % i == 0:
				x //= i
		i += 1
	if x > 1:
		ans = ans * (x - 1) // x
	return ans

def solve():
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	m //= g
	print(totient(m))
	return
t = 1
t = int(input())
while t > 0:
	t -= 1
	solve()


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 *
from collections import *
t = int(input())
for y in range(t):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	m1 = m // g
	i = 2
	ans = m1
	while i * i <= m1:
		if m1 % i == 0:
			ans //= i
			ans *= i - 1
		while m1 % i == 0:
			m1 //= i
		i += 1
	if m1 > 1:
		ans //= m1
		ans *= m1 - 1
	print(ans)


from functools import reduce
from itertools import combinations
from operator import mul

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

def primes(n):
	p = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			p.append(i)
			while n % i == 0:
				n = n // i
		if i > n:
			break
	if n > 1:
		p.append(n)
	return p

def copr(n, k, p=None):
	if p is None:
		p = primes(n)
	res = 0
	for c in range(1, len(p) + 1):
		sig = 1 if c % 2 else -1
		for v in combinations(p, c):
			res += sig * (k // reduce(mul, v))
	return k - res

def go():
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	a = a // g
	m = m // g
	p = primes(m)
	return copr(m, m, p)
T = int(input())
for _ in range(T):
	print(go())


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

def phi(a):
	(tmp, ans) = (a, a)
	d = 2
	while d * d <= tmp:
		cnt = 0
		while tmp % d == 0:
			tmp /= d
			cnt += 1
		if cnt > 0:
			ans -= ans / d
		d += 1
	if tmp > 1:
		ans -= ans / tmp
	return int(ans)
for t in range(int(input())):
	(a, m) = map(int, input().split(' '))
	print(phi(m / gcd(a, m)))


from collections import defaultdict

def totient(n):
	primes = defaultdict(int)
	d = 2
	diver = n
	while d * d <= n:
		while diver % d == 0:
			primes[d] += 1
			diver //= d
		d += 1
	if diver != 1:
		primes[diver] += 1
	tot = 1
	for (p, k) in primes.items():
		tot *= (p - 1) * p ** (k - 1)
	return tot

def gcd(a, b):
	while a % b != 0:
		a %= b
		(a, b) = (b, a)
	return b
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	print(totient(m // gcd(a, m)))


import math

def factorize(n):
	count = 0
	res = []
	while (n % 2 > 0) == False:
		n >>= 1
		count += 1
	if count > 0:
		res.append(2)
	for i in range(3, int(math.sqrt(n)) + 1):
		count = 0
		while n % i == 0:
			count += 1
			n = int(n / i)
		if count > 0:
			res.append(i)
		i += 2
	if n > 2:
		res.append(n)
	return res
t = int(input())
for i in range(t):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	p = a // g
	q = m // g
	div = factorize(q)
	div.sort(reverse=True)
	b = []
	j = 0
	pr = 1
	while j < len(div):
		b.append(pr * div[j])
		pr *= b[j]
		j += 1
	pr = 1
	j = 0
	while j < len(div):
		pr *= div[j]
		j += 1
	j = 1
	div = []
	while j <= math.sqrt(pr):
		if pr % j == 0:
			div.append(j)
			div.append(pr // j)
		j += 1
	div = sorted(list(set(div)))
	div.pop(0)
	j = 0
	res1 = 0
	res2 = 0
	curr = 0
	while j < len(div):
		z = len(factorize(div[j]))
		if z % 2 == 1:
			res1 += math.floor((p + q - 1) / div[j])
			res2 += math.floor((p - 1) / div[j])
		else:
			res1 -= math.floor((p + q - 1) / div[j])
			res2 -= math.floor((p - 1) / div[j])
		j += 1
	print(q - (res1 - res2))


import math

def lcm(a, b):
	ans = a * b // math.gcd(a, b)
	return ans
T = int(input())
for _ in range(T):
	(a, m) = map(int, input().split())
	t = math.gcd(a, m)
	ans = m // t
	fnl = m // t
	for i in range(2, int(math.sqrt(m) + 1)):
		if ans % i == 0:
			while ans % i == 0:
				ans = ans // i
			fnl -= fnl // i
	if ans > 1:
		fnl -= fnl // ans
	print(fnl)


import math as m

def phi(n):
	ans = n
	t = int(m.sqrt(n))
	for i in range(2, t + 1):
		if n % i == 0:
			ans = ans * (i - 1) // i
			while n % i == 0:
				n //= i
	if n > 1:
		ans //= n
		ans *= n - 1
	return ans
t = int(input())
for ti in range(t):
	(n, x) = (int(i) for i in input().split(' '))
	x //= m.gcd(n, x)
	print(phi(x))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for y in range(t):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	m1 = m // g
	i = 2
	ans = m1
	while i * i <= m1:
		if m1 % i == 0:
			ans //= i
			ans *= i - 1
		while m1 % i == 0:
			m1 //= i
		i += 1
	if m1 > 1:
		ans //= m1
		ans *= m1 - 1
	print(ans)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 998244353
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def func(m):
	x = []
	for i in range(2, int(sqrt(m)) + 1):
		c = 0
		while m % i == 0:
			m //= i
			c += 1
		if c > 0:
			x.append(i)
	if m > 1:
		x.append(m)
	return x

def solve():
	for _ in range(ii()):
		(a, m) = mi()
		r = a + m - 1

		def get(g):
			return r // g - (a - 1) // g
		gcd1 = gcd(a, m)
		tot = get(gcd1)
		m //= gcd1
		x = func(m)
		n = len(x)
		sub = 0
		for i in range(1, 1 << n):
			(c, g) = (0, 1)
			for j in range(n):
				if i >> j & 1:
					g1 = gcd(g, x[j])
					g = g * x[j] // g1
					c += 1
			if c & 1:
				sub += get(g * gcd1)
			else:
				sub -= get(g * gcd1)
		print(tot - sub)
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


from math import sqrt, gcd
from collections import Counter

def primeFactors(n):
	res = Counter()
	while n % 2 == 0:
		res[2] += 1
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			res[i] += 1
			n = n // i
	if n > 2:
		res[n] += 1
	return res

def main():

	def solve():
		(a, m) = map(int, input().split())
		g = gcd(a, m)
		mm = m // g
		pf = primeFactors(mm)
		etnum = mm
		etdenom = 1
		for p in pf:
			etnum *= p - 1
			etdenom *= p
		print(etnum // etdenom)
	q = int(input())
	for _ in range(q):
		solve()
main()


import os, sys, math, random
T = int(input())
(a, m, g) = (0, 0, 0)
(a0, m0) = (0, 0)

def de(n):
	r = int(n ** 0.5) + 1
	res = []
	for i in range(2, r):
		if n % i == 0:
			res.append(i)
			while n % i == 0:
				n /= i
	if n >= 2:
		res.append(n)
	return res

def cal(ub, ds):
	ld = len(ds)
	res = 0
	for i in range(1, 1 << ld):
		(dv, dn) = (1, 0)
		for j in range(0, ld):
			if i & 1 << j > 0:
				dv *= ds[j]
				dn += 1
		cur = int(ub / dv) + 1
		if dn % 2 == 0:
			cur *= -1
		res += cur
	return ub + 1 - res

def solve():
	global a, m, g
	g = math.gcd(a, m)
	(a, m) = (int(a / g), int(m / g))
	(lb, ub) = (a - 1, m + a - 1)
	ds = de(m)
	return cal(ub, ds) - cal(lb, ds)
for _ in range(T):
	(a, m) = map(int, input().split())
	(a0, m0) = (a, m)
	print(solve())


import itertools
import math
t = int(input())

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
for _ in range(t):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	a //= g
	m //= g
	l = factorization(m)
	ans = m
	if len(l) == 1 and l[0][1] == 1:
		print(m - 1)
		continue
	else:
		for (i, j) in l:
			ans //= i
			ans *= i - 1
	print(ans)


import sys
from math import gcd
from collections import Counter
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	m //= g
	factorization = Counter()
	while not m & 1:
		factorization[2] += 1
		m >>= 1
	limit = int(m ** 0.5) + 1
	f = 3
	while f < limit and f <= m:
		while m % f == 0:
			factorization[f] += 1
			m //= f
		f += 2
	if m > 1:
		factorization[m] += 1
	phi = 1
	for (prime, power) in factorization.items():
		phi *= (prime - 1) * prime ** (power - 1)
	print(phi)


import math

def factors(n):
	d = 2
	while d * d <= n:
		if n % d == 0:
			yield d
		while n % d == 0:
			n //= d
		d += 1
	if n > 1:
		yield n
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	ans = m // g
	for p in factors(m // g):
		ans -= ans // p
	print(ans)


from math import gcd

def euler_phi(n):
	res = n
	for x in range(2, int(n ** 0.5) + 1):
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	m = m // gcd(a, m)
	print(euler_phi(m))


import math

def phi(n):
	ans = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			ans //= i
			ans *= i - 1
		while n % i == 0:
			n //= i
		i += 1
	if n >= 2:
		ans //= n
		ans *= n - 1
		n //= n
	return ans
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	ans = phi(m / g)
	print(int(ans))


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction

def solve(x):
	(b, p, i) = (set(), x, 2)
	while i * i <= x:
		if x % i:
			i += 1
		else:
			x = x // i
			b.add(i)
	if x > 1:
		b.add(x)
	for i in b:
		p = p * (i - 1) // i
	return p

def main():
	for _ in range(int(input())):
		(a, m) = map(int, input().split())
		g = gcd(a, m)
		t = m // g
		z = solve(t)
		l = a // g // t * z
		r = ((m - 1) // g + a // g) // t * z
		print(r - l)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


INF = 10 ** 10

def main():
	print = out.append
	(a, b) = get_list()
	print(phi(b // math.gcd(a, b)))

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = int(n / p)
			result -= int(result / p)
		p += 1
	if n > 1:
		result -= int(result / n)
	return result
import sys
import math
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
[main() for _ in range(int(input()))]
print(*out, sep='\n')


import sys, math, itertools
input = sys.stdin.readline
T = int(input())

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b:
		r = a % b
		(a, b) = (b, r)
	return a
for _ in range(T):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	D = set()
	k = m // g
	while True:
		if k == 1:
			break
		q = k
		for i in range(2, int(math.sqrt(k)) + 2):
			if k % i == 0:
				D.add(i)
				k //= i
				break
		if k == q:
			D.add(k)
			break
	P = a + m - 1
	Q = a - 1
	ans = P // g
	diff = Q // g
	for i in range(1, len(D) + 1):
		for q in itertools.combinations(D, i):
			qq = 1
			for z in q:
				qq *= z
			if i & 1:
				ans -= P // (qq * g)
				diff -= Q // (qq * g)
			else:
				ans += P // (qq * g)
				diff += Q // (qq * g)
	print(ans - diff)


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)


def Same_GCDs(a, m):
	d = MCD(a, m)
	return Phi(m // d)

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

def Descomp_En_Primos(n):
	factPrimos = []
	if n % 2 == 0:
		exp = 0
		while n % 2 == 0:
			n //= 2
			exp += 1
		factPrimos.append((2, exp))
	for i in range(3, n + 1, 2):
		if i * i > n:
			factPrimos.append((n, 1))
			break
		if n % i == 0:
			exp = 0
			while n % i == 0:
				n //= i
				exp += 1
			factPrimos.append((i, exp))
			if n == 1:
				break
	return factPrimos

def Es_Primo(n):
	if n == 2:
		return True
	for i in range(2, int(n ** 1 / 2) + 1):
		if n % i == 0:
			return False
	return True

def Phi(n):
	factores_primos = Descomp_En_Primos(n)
	phi = n
	for i in range(0, len(factores_primos)):
		phi = phi - phi // factores_primos[i][0]
	return phi
t = int(input())
while t > 0:
	_input = [int(x) for x in input().split()]
	a = _input[0]
	m = _input[1]
	print(Same_GCDs(a, m))
	t -= 1


import math

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

def phi(val):
	ret = 1
	for i in range(2, int(math.sqrt(val)) + 1):
		if val % i == 0:
			c = 0
			while val % i == 0:
				val //= i
				c += 1
			ret *= i - 1
			for j in range(1, c):
				ret *= i
	if val > 1:
		ret *= val - 1
	return ret
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	g = __gcd(a, m)
	print(phi(m // g))


import os, sys
from io import BytesIO, IOBase
from itertools import combinations
from math import gcd
from functools import reduce

def main():
	for _ in range(int(input())):
		(a, m) = map(int, input().split())
		y = gcd(a, m)
		m1 = m
		m //= y
		fac = []
		if not m % 2:
			fac.append(2)
		while not m % 2:
			m //= 2
		for i in range(3, int(m ** 0.5) + 1, 2):
			if not m % i:
				fac.append(i)
			while not m % i:
				m //= i
		if m != 1:
			fac.append(m)
		ans = (a + m1 - 1) // y - (a - 1) // y
		s = 1
		for x in range(1, len(fac) + 1):
			s *= -1
			for j in combinations(fac, x):
				yy = reduce(lambda aa, bb: aa * bb, j) * y
				ans += s * ((a + m1 - 1) // yy - (a - 1) // yy)
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
from collections import Counter

def primeFactors(n):
	assert n >= 1
	factors = Counter()
	while n % 2 == 0:
		factors[2] += 1
		n //= 2
	x = 3
	while x * x <= n:
		while n % x == 0:
			factors[x] += 1
			n //= x
		x += 2
	if n != 1:
		factors[n] += 1
	return factors

def primePowPhi(p, k):
	if k == 0:
		return 1
	return p ** (k - 1) * (p - 1)

def phi(n):
	ret = 1
	for (p, k) in primeFactors(n).items():
		ret *= primePowPhi(p, k)
	return ret

def solve(a, m):
	g = math.gcd(a, m)
	A = a // g
	M = m // g
	if False:
		ans = set()
		for x in range(m):
			if math.gcd(a, m) == math.gcd(a + x, m):
				ans.add(x)
		ans2 = set()
		for K in range(A, A + M):
			if math.gcd(K, M) == 1:
				x = g * (K - A)
				ans2.add(x)
		assert ans == ans2
		assert phi(M) == len(ans)
	return phi(M)
T = int(input())
for t in range(T):
	(a, m) = [int(x) for x in input().split()]
	ans = solve(a, m)
	print(ans)


from collections import Counter
from math import gcd

def get_prime_set(ub):
	from itertools import chain
	from math import sqrt
	if ub < 4:
		return ({}, {}, {2}, {2, 3})[ub]
	(ub, ub_sqrt) = (ub + 1, int(sqrt(ub)) + 1)
	primes = {2, 3} | set(chain(range(5, ub, 6), range(7, ub, 6)))
	du = primes.difference_update
	for n in chain(range(5, ub_sqrt, 6), range(7, ub_sqrt, 6)):
		if n in primes:
			du(range(n * 3, ub, n * 2))
	return primes
primes = get_prime_set(10 ** 5 + 10)
for _ in range(int(input())):
	(_a, _m) = map(int, input().split())
	(a, m) = (_a, _m)
	(d1, d2) = (Counter(), Counter())
	for p in primes:
		while a % p == 0:
			d1[p] += 1
			a //= p
		while m % p == 0:
			d2[p] += 1
			m //= p
	if a > 1:
		d1[a] += 1
	if m > 1:
		d2[m] += 1
	(a, m) = (_a, _m)
	g = gcd(a, m)
	ans = (a + m - 1) // g - (a - 1) // g
	d = []
	for (k, v) in d2.items():
		if d1[k] < v:
			d.append(k)
	len_d = len(d)
	for bit in range(1, 2 ** len_d):
		popcount = 0
		cnt = 0
		div = g
		for i in range(len_d):
			if bit & 1 << i:
				popcount ^= 1
				div *= d[i]
		cnt += (a + m - 1) // div - (a - 1) // div
		ans += -cnt if popcount else cnt
	print(ans)


from collections import defaultdict
from math import gcd

def Primes(M):
	prime = {i for i in range(2, M)}
	for i in range(2, M):
		if i in prime:
			for j in range(i * 2, M, i):
				if j in prime:
					prime.remove(j)
	return prime
primes = Primes(10 ** 5)

def solve():
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	G = m // g
	d = defaultdict(int)
	for p in primes:
		while G % p == 0:
			d[p] += 1
			G //= p
	if G > 1:
		d[G] = 1
	res = m // g
	for v in d.keys():
		res *= v - 1
		res //= v
	print(res)
	return

def main():
	t = int(input())
	for i in range(t):
		solve()
	return
main()


import math as m

def phi(n):
	res = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			res -= res // i
		i += 1
	if n > 1:
		res -= res // n
	return res
t = int(input())
for tc in range(t):
	(a, b) = map(int, input().split())
	g = m.gcd(a, b)
	print(phi(b // g))


import random

def primesbelow(N):
	correction = N % 6 > 1
	N = {0: N, 1: N - 1, 2: N + 4, 3: N + 3, 4: N + 2, 5: N + 1}[N % 6]
	sieve = [True] * (N // 3)
	sieve[0] = False
	for i in range(int(N ** 0.5) // 3 + 1):
		if sieve[i]:
			k = 3 * i + 1 | 1
			sieve[k * k // 3::2 * k] = [False] * ((N // 6 - k * k // 6 - 1) // k + 1)
			sieve[(k * k + 4 * k - 2 * k * (i % 2)) // 3::2 * k] = [False] * ((N // 6 - (k * k + 4 * k - 2 * k * (i % 2)) // 6 - 1) // k + 1)
	return [2, 3] + [3 * i + 1 | 1 for i in range(1, N // 3 - correction) if sieve[i]]
smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000

def isprime(n, precision=7):
	if n < 1:
		raise ValueError('Out of bounds, first argument must be > 0')
	elif n <= 3:
		return n >= 2
	elif n % 2 == 0:
		return False
	elif n < _smallprimeset:
		return n in smallprimeset
	d = n - 1
	s = 0
	while d % 2 == 0:
		d //= 2
		s += 1
	for repeat in range(precision):
		a = random.randrange(2, n - 2)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for r in range(s - 1):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				break
		else:
			return False
	return True

def pollard_brent(n):
	if n % 2 == 0:
		return 2
	if n % 3 == 0:
		return 3
	(y, c, m) = (random.randint(1, n - 1), random.randint(1, n - 1), random.randint(1, n - 1))
	(g, r, q) = (1, 1, 1)
	while g == 1:
		x = y
		for i in range(r):
			y = (pow(y, 2, n) + c) % n
		k = 0
		while k < r and g == 1:
			ys = y
			for i in range(min(m, r - k)):
				y = (pow(y, 2, n) + c) % n
				q = q * abs(x - y) % n
			g = gcd(q, n)
			k += m
		r *= 2
	if g == n:
		while True:
			ys = (pow(ys, 2, n) + c) % n
			g = gcd(abs(x - ys), n)
			if g > 1:
				break
	return g
smallprimes = primesbelow(1000)

def primefactors(n, sort=False):
	factors = []
	for checker in smallprimes:
		while n % checker == 0:
			factors.append(checker)
			n //= checker
		if checker > n:
			break
	if n < 2:
		return factors
	while n > 1:
		if isprime(n):
			factors.append(n)
			break
		factor = pollard_brent(n)
		factors.extend(primefactors(factor))
		n //= factor
	if sort:
		factors.sort()
	return factors

def factorization(n):
	factors = {}
	for p1 in primefactors(n):
		try:
			factors[p1] += 1
		except KeyError:
			factors[p1] = 1
	return factors
totients = {}

def totient(n):
	if n == 0:
		return 1
	try:
		return totients[n]
	except KeyError:
		pass
	tot = 1
	for (p, exp) in factorization(n).items():
		tot *= (p - 1) * p ** (exp - 1)
	totients[n] = tot
	return tot

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

def solve():
	t = int(input())
	for _ in range(t):
		(a, m) = (int(i) for i in input().strip().split(' '))
		k = gcd(a, m)
		print(totient(m // k))
solve()


from math import gcd
from sys import stdout
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
print = stdout.write
primes = []
n = 10 ** 5 + 1
mark = [True] * n
for i in range(2, n):
	if mark[i]:
		primes.append(i)
		for j in range(i, n, i):
			mark[j] = False
del mark
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	m //= gcd(a, m)
	ans = m
	for i in primes:
		if m == 1:
			break
		if m % i == 0:
			ans -= ans // i
			while m % i == 0:
				m //= i
	else:
		ans -= ans // m
	print(str(ans) + '\n')


import math, collections, sys
input = sys.stdin.readline

def totient(x):
	result = x
	p = 2
	while p * p <= x:
		if x % p == 0:
			while x % p == 0:
				x = x // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if x > 1:
		result = result * (1.0 - 1.0 / float(x))
	return int(result)
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	g = math.gcd(a, m)
	print(totient(m // g))


from math import gcd, sqrt

def primeFactors(n, s):
	while n % 2 == 0:
		s.add(2)
		n //= 2
	x = int(sqrt(n)) + 1
	for i in range(3, x, 2):
		while n % i == 0:
			s.add(i)
			n //= i
	if n > 2:
		s.add(n)
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	s = set({})
	m2 = m // g
	primeFactors(m2, s)
	s = list(s)
	n = len(s)
	count1 = 0
	for i in range(2 ** n):
		b = bin(i)[2:]
		b = '0' * (n - len(b)) + b
		count = 0
		prod = g
		for j in range(n):
			if b[j] == '1':
				count += 1
				prod *= s[j]
		if count % 2 == 0:
			count1 += (a + m - 1) // prod
		else:
			count1 -= (a + m - 1) // prod
	count2 = 0
	for i in range(2 ** n):
		b = bin(i)[2:]
		b = '0' * (n - len(b)) + b
		count = 0
		prod = g
		for j in range(n):
			if b[j] == '1':
				count += 1
				prod *= s[j]
		if count % 2 == 0:
			count2 += (a - 1) // prod
		else:
			count2 -= (a - 1) // prod
	print(count1 - count2)


from math import gcd
from sys import stdin
from itertools import combinations

def count_multiples(k, n):
	return (n - n % k) // k

def count_prime_multiples(n, primes):
	c = 0
	for i in range(1, len(primes) + 1):
		for subset in combinations(primes, i):
			product = 1
			for p in subset:
				product *= p
			multiples = count_multiples(product, n)
			if i % 2 == 0:
				c -= multiples
			else:
				c += multiples
	return c

def prime_factors(n):
	primes = set()
	k = 2
	rem = n
	while k * k <= n:
		while rem % k == 0:
			primes.add(k)
			rem //= k
		k += 1
	if rem > 1:
		primes.add(rem)
	return primes

def coprime_upto_naive(n, k):
	c = 0
	for a in range(1, n + 1):
		if gcd(a, k) == 1:
			c += 1
	return c

def coprime_upto_fast(n, k):
	primes = prime_factors(k)
	multiples = count_prime_multiples(n, primes)
	return n - multiples
n = int(input())
for i in range(n):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	lower_limit = a // g - 1
	upper_limit = (a + m) // g - 1
	k = m // g
	print(coprime_upto_fast(upper_limit, k) - coprime_upto_fast(lower_limit, k))


def primeFactor(N):
	i = 2
	ret = {}
	n = N
	mrFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:

			def findFactorRho(N):

				def gcd(a, b):
					while b:
						(a, b) = (b, a % b)
					return a

				def f(x, c):
					return (x * x + c) % N
				for c in range(1, 99):
					(X, d, j) = ([2], 1, 0)
					while d == 1:
						j += 1
						X.append(f(X[-1], c))
						X.append(f(X[-1], c))
						d = gcd(abs(X[2 * j] - X[j]), N)
					if d != N:
						if isPrimeMR(d):
							return d
						elif isPrimeMR(N // d):
							return N // d
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					mrFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if mrFlg > 0:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def isPrimeMR(n):
	if n == 2:
		return True
	if n == 1 or n & 1 == 0:
		return False
	d = n - 1 >> 1
	while d & 1 == 0:
		d >>= 1
	L = [2, 7, 61] if n < 1 << 32 else [2, 13, 23, 1662803] if n < 1 << 40 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
	for a in L:
		t = d
		y = pow(a, t, n)
		while t != n - 1 and y != 1 and (y != n - 1):
			y = y * y % n
			t <<= 1
		if y != n - 1 and t & 1 == 0:
			return False
	return True

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
T = int(input())
for _ in range(T):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	n = m // g
	pf = primeFactor(n)
	ans = 1
	for p in pf:
		ans *= (p - 1) * p ** (pf[p] - 1)
	print(ans)


import math

def divisors(n):
	res = []
	d = 1
	while d * d <= n:
		if n % d == 0:
			res.append(d)
			if d != n // d:
				res.append(n // d)
		d = d + 1
	return res

def u(n):
	if n == 1:
		return 1
	d = 2
	divs = 0
	count = 0
	while d * d <= n:
		if n % d == 0:
			n = n // d
			divs += 1
			if count == 1:
				return 0
			else:
				count = 1
		else:
			d = d + 1
			count = 0
	if n > 1:
		if n == d and count == 1:
			return 0
		divs += 1
	if divs % 2 == 0:
		return 1
	else:
		return -1
t = int(input())
for i in range(t):
	am = list(map(int, input().split()))
	a = am[0]
	m = am[1]
	g = math.gcd(a, m)
	divs = divisors(m // g)
	sum = 0
	for div in divs:
		sum += u(div) * (m // g // div)
	print(sum)


T = int(input())

def gen_prime(n):
	primes = []
	factor = [0] * n
	for i in range(2, n):
		if factor[i] == 0:
			factor[i] = i
			primes.append(i)
		for j in primes:
			if j * i >= n:
				break
			factor[j * i] = j
			if i % j == 0:
				break
	return primes

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

def prime_factorize(a, primes):
	m_primes = []
	for p in primes:
		if a % p == 0:
			m_primes.append(p)
			while a % p == 0:
				a //= p
	if a > 1:
		m_primes.append(a)
	return m_primes

def count_coprime(m, n_primes):
	k = len(n_primes)
	s = 0
	for i in range(1 << k):
		z = 1
		y = 0
		for j in range(k):
			if 1 << j & i != 0:
				z *= n_primes[j]
				y += 1
		if y % 2 == 1:
			s -= m // z
		else:
			s += m // z
	return s
primes = gen_prime(100010)
for _ in range(T):
	(n, m) = list(map(int, input().split()))
	g = gcd(n, m)
	a = n // g
	b = m // g
	r = count_coprime(a + b - 1, prime_factorize(b, primes))
	s = count_coprime(a - 1, prime_factorize(b, primes))
	print(r - s)


from math import gcd
q = int(input())
for j in range(q):
	(a, m) = map(int, input().split())
	g = gcd(a, m)
	a //= g
	m //= g
	ans = m
	i = 2
	while i * i <= m:
		if m % i == 0:
			while m % i == 0:
				m //= i
			ans -= ans // i
		i += 1
	if m > 1:
		ans -= ans // m
	print(ans)


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	n = a // b
	r = a % b
	if r == 0:
		return b
	return gcd(b, r)

def gcds(a, m):
	d = gcd(a, m)
	n = m // d
	add_primes(n)
	ans = n
	n0 = n
	for p in primes:
		if n0 % p == 0:
			ans = ans * (p - 1) // p
		while n0 % p == 0:
			n0 = n0 // p
	if n0 != 1:
		ans = ans * (n0 - 1) // n0
	if ans == n:
		ans = ans - 1
	return int(max(1, ans))

def is_prime(n):
	for p in primes:
		if p * p > n:
			break
		if n % p == 0:
			return False
	return True

def add_primes(n):
	for i in range(n):
		if i * i > n:
			break
		if i < primes[-1]:
			continue
		if is_prime(i):
			primes.append(i)
primes = [2, 3, 5, 7]
t = int(input())
for _ in range(t):
	(a, m) = [int(s) for s in input().split(' ')]
	print(gcds(a, m))


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
prime = getPrimes()

def solve(n):
	res = n
	for i in prime:
		while n % i == 0:
			res //= i
			res *= i - 1
			while n % i == 0:
				n //= i
	if n > 1:
		res /= n
		res *= n - 1
	return int(res)
for i in ' ' * getInt():
	(n, m) = zzz()
	p = gcd(n, m)
	print(solve(m // p))


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)
for i in range(ii()):
	(a, b) = mi()
	e = gcd(a, b)
	print(phi(b // e))


from sys import stdin
import math
for case in range(int(stdin.readline())):
	(a, m) = [int(x) for x in stdin.readline().split()]
	aFactors = []
	mFactors = []
	for x in range(1, int(math.sqrt(a)) + 1):
		if a % x == 0:
			aFactors.append(x)
			aFactors.append(a // x)
	for x in range(1, int(math.sqrt(m)) + 1):
		if m % x == 0:
			mFactors.append(x)
			mFactors.append(m // x)
	aFactors.sort(reverse=True)
	mFactors.sort(reverse=True)
	mSet = set(mFactors)
	for x in aFactors:
		if x in mSet:
			gcd = x
			break
	a2 = a // gcd
	m2 = m // gcd
	m2Factors = []
	for x in range(1, int(math.sqrt(m2)) + 1):
		if m2 % x == 0:
			if x != 1:
				m2Factors.append(x)
			if m2 // x != x:
				m2Factors.append(m2 // x)
	total = m2
	primeFactors = []
	for f in m2Factors:
		v = True
		for h in m2Factors:
			if h != f and f % h == 0:
				v = False
				break
		if v:
			primeFactors.append(f)
	things = []
	for x in range(len(primeFactors)):
		for y in range(len(things)):
			things.append((things[y][0] * primeFactors[x], things[y][1] + 1))
		things.append((primeFactors[x], 0))
	for (x, order) in things:
		if order % 2 == 1:
			total += (m2 + a2 - 1) // x - (a2 - 1) // x
		else:
			total -= (m2 + a2 - 1) // x - (a2 - 1) // x
	print(total)


import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

def input():
	return sys.stdin.readline().strip()

def resolve():
	t = int(input())

	def euler_phi(n):
		result = n
		p = 2
		while p * p <= n:
			if n % p == 0:
				while n % p == 0:
					n = int(n / p)
				result -= int(result / p)
			p += 1
		if n > 1:
			result -= int(result / n)
		return result
	for i in range(t):
		(a, m) = map(int, input().split())
		g = math.gcd(a, m)
		mm = m // g
		print(euler_phi(mm))
resolve()


import sys
from math import gcd
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
uu = t

def gets(l, d):
	return l // d

def getrange(l, r, d):
	return gets(r, d) - gets(l - 1, d)
while t > 0:
	t -= 1
	(a, n) = mi()
	(l, r) = (a, n)
	g = gcd(a, n)
	i = 2
	d = []
	p = n // g
	while i * i <= p:
		if p % i == 0:
			d.append(i)
			while p % i == 0:
				p //= i
		i += 1
	if p > 1:
		d.append(p)
	ans = 0
	for i in range(1, 2 ** len(d)):
		h = bin(i)[2:]
		h = (len(d) - len(h)) * '0' + h
		w = []
		p = 0
		c = g
		for j in range(len(d)):
			if h[j] == '1':
				c *= d[j]
				p += 1
		if p % 2:
			ans += getrange(l, l + r - 1, c)
		else:
			ans -= getrange(l, l + r - 1, c)
	print(getrange(l, l + r - 1, g) - ans)


import math
import collections

def solve():
	(a, m) = map(int, input().split())
	primes = []
	t = math.gcd(a, m)
	(ta, tm) = (a // t, m // t)
	t = tm
	for i in range(2, 1 + int(math.sqrt(t))):
		if t % i:
			continue
		primes.append(i)
		while t % i == 0:
			t = t // i
	if t > 1:
		primes.append(t)

	def getSum(threshold):
		mask = [0]
		cnt = [0]
		ans = [1]
		res = [0]

		def dfs(start, ans, res, mask, cnt):
			n = len(primes)
			if ans[0] > 1:
				sign = 1
				if cnt[0] % 2 == 0:
					sign = -sign
				res[0] += sign * (threshold - 1) // ans[0]
			if start >= n:
				return
			for i in range(start, n):
				tmm = 1 << i
				if mask[0] & tmm:
					continue
				mask[0] += tmm
				cnt[0] += 1
				ans[0] *= primes[i]
				dfs(i + 1, ans, res, mask, cnt)
				mask[0] -= tmm
				cnt[0] -= 1
				ans[0] = ans[0] // primes[i]
		dfs(0, ans, res, mask, cnt)
		return res[0]
	print(tm - getSum(ta + tm) + getSum(ta))

def main():
	T = 1
	T = int(input())
	while T:
		solve()
		T -= 1
main()


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))))


import sys
from collections import Counter
readline = sys.stdin.readline

def popcount(i):
	assert 0 <= i < 4294967296
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

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

def prsh(N):
	prime = [2]
	for L in range(3, N):
		for p in prime:
			if not L % p:
				break
			if p > L ** (1 / 2):
				prime.append(L)
				break
	return prime
primes = prsh(222222)

def munum(N):
	C = Counter()
	diviprimes = []
	cnt = 0
	p = 0
	while N >= p ** 2:
		p = primes[cnt]
		if N % p == 0:
			diviprimes.append(p)
			N //= p
			while N % p == 0:
				N //= p
		cnt += 1
	if N != 1:
		diviprimes.append(N)
	M = len(diviprimes)
	for i in range(1 << M):
		res = 1
		k = popcount(i)
		for j in range(M):
			if i & 1 << j:
				res *= diviprimes[j]
		C[res] = (-1) ** k
	return C

def calc(x, l):
	L = munum(l)
	res = 0
	for (k, v) in L.items():
		res += v * (x // k)
	return res
Qu = int(readline())
Ans = [None] * Qu
for qu in range(Qu):
	(a, m) = map(int, readline().split())
	d = gcd(a, m)
	k1 = a // d - 1
	k2 = (a + m - 1) // d
	l = m // d
	Ans[qu] = calc(k2, l) - calc(k1, l)
print('\n'.join(map(str, Ans)))


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

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
	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))