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.
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)	
	#print(d,g)
	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)			
