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 sys import stdin, stdout
from math import gcd
input = stdin.readline
#print = stdout.write

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(h(m - 1), h(a - 1), p)
	print(m - h(m))
