You are given two integers a and m. Calculate the number of integers x such that 0 ≤ x < m and \gcd(a, m) = \gcd(a + x, m).

Note: \gcd(a, b) is the greatest common divisor of a and b.

Input

The first line contains the single integer T (1 ≤ T ≤ 50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and m (1 ≤ a < m ≤ 10^{10}).

Output

Print T integers — one per test case. For each test case print the number of appropriate x-s.

Example

Input


3
4 9
5 10
42 9999999967


Output


6
1
9999999966

Note

In the first test case appropriate x-s are [0, 1, 3, 4, 6, 7].

In the second test case the only appropriate x is 0.
from math import 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)
	# print(s)
	n = len(s)


	count1 = 0
	for i in range(2**n):
		b = bin(i)[2:]
		b = '0'*(n-len(b)) + b
		# print(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)

