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.
"""
// Author : snape_here - Susanta Mukherjee
     
"""
 
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

# Python 3 program to calculate 
# Euler's Totient Function 
# using Euler's product formula 

def phi(n) : 

	result = n # Initialize result as n 
	
	# Consider all prime factors 
	# of n and for every prime 
	# factor p, multiply result with (1 - 1 / p) 
	p = 2
	while(p * p<= n) : 

		# Check if p is a prime factor. 
		if (n % p == 0) : 

			# If yes, then update n and result 
			while (n % p == 0) : 
				n = n // p 
			result = result * (1.0 - (1.0 / (float) (p))) 
		p = p + 1
		
		
	# If n has a prime factor 
	# greater than sqrt(n) 
	# (There can be at-most one 
	# such prime factor) 
	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))