Chef recently created a new Tiling Window Manager called ChefWM. He wants to find out the maximum number of columns of windows he can fit on the screen and he needs your help.

Consider the screen to be an axis-aligned rectangle in the xy-plane, with its bottom-left corner at (0, 0) and top-right corner at (N, M) (that is, the screen has width N units and height M units). ChefWM works as follows:

First, the screen is divided into one or more columns of equal integer width.
Then, each column is divided into two or more windows of equal integer height. Note that all windows within a column must have the same height, but windows in different columns may have different heights.
Finally, Chef would like the following condition to hold:
- No two windows from different columns can have their horizontal boundary share the same y-coordinate (apart from y = 0 and y = M). See the figures below for more details.

It is not allowed to leave any empty space on the screen, i.e, the division performed in the first two steps above must cover the entire screen.

Here is an example of a tiling that satisfies all the conditions, for N = 8 and M = 6.

Below are two tilings that satisfy all conditions except the last. The one on the left has a horizontal edge at y = 2 in both columns, while the one on the right has a horizontal edge at y = 2 in column 1 and column 3.

What is the maximum number of *columns* that ChefWM can fit on the screen while following the above conditions? Note that you do not need to maximize the number of windows, you only need to maximize the number of columns.

It may be possible that no columns can be created under these conditions, in that case, print 0.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input, containing two space-separated integers N, M — the coordinates of the top-right corner of the screen.

------ Output Format ------ 

For each test case, output a single line containing one integer — the maximum number of columns ChefWM can create for the screen.

------ Constraints ------ 

$1 ≤ T ≤ 500$
$1 ≤ N ≤ 10^{9}$
$1 ≤ M ≤ 10^{9}$

----- Sample Input 1 ------ 
5
8 210
1 100
100 5
10 1
9 2310

----- Sample Output 1 ------ 
4
1
1
0
3

----- explanation 1 ------ 
Test Case 1: It is possible to make $4$ columns as follows:
- The first column has $7$ windows of height $30$ each
- The second column has $2$ windows of height $105$ each
- The third column has $5$ windows of height $42$ each
- The last column has $3$ windows of height $70$ each

It can be seen in the diagram below that the edges from any two windows from different columns do not have the same $y$-coordinate except for $y=0$ and $y=m$.   

Test Case 2: There can only be one column no matter how many windows you keep (as long as there are at least $2$ windows).

Test Case 3: You can have a single column with $5$ windows. It can be shown that this is the maximum number of columns that can possibly satisfy the given restrictions.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def unique_prime_factors(n):
	count = 0
	i = 2
	while i ** 2 <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n /= i
		i += 1
	if n != 1:
		count += 1
	return count
t = int(input())
while t:
	(n, m) = map(int, input().split())
	prm_fac = unique_prime_factors(m)
	ans = 0
	i = prm_fac
	while i > 0:
		if n % i == 0:
			ans = i
			break
		i -= 1
	print(ans)
	t -= 1


t = int(input())
while t:
	(n, m) = map(int, input().split())
	c = 0
	for i in range(2, int(m ** 0.5) + 1):
		if m % i == 0:
			c += 1
			while m % i == 0:
				m = m // i
	if m != 1:
		c += 1
	if c == 0:
		print(c)
	elif n % c == 0:
		print(c)
	else:
		while n % c != 0:
			c -= 1
		print(c)
	t -= 1


def makePr(p_limit):
	track = [False, True] * (p_limit // 2 + 1)
	if p_limit % 2 == 0:
		track.pop()
	track[0:3] = [False, False, True]
	pc = 3
	while pc * pc <= p_limit:
		if track[pc]:
			for a in range(pc * pc, p_limit + 1, 2 * pc):
				track[a] = False
		pc += 2
	return [n for (n, p) in enumerate(track) if p]

def get_cols(N, M, prs):
	if M == 1:
		return 0
	Nlowfac = [1]
	for f in range(2, 10):
		if N % f == 0:
			Nlowfac.append(f)
	if len(Nlowfac) == 1:
		return 1
	Mlim = int((M + 1) ** 0.5)
	Mred = M
	dpf = 0
	for p in prs:
		if Mred % p == 0:
			dpf += 1
			if dpf == Nlowfac[-1]:
				return dpf
			while Mred % p == 0:
				Mred //= p
			Mlim = int((Mred + 1) ** 0.5)
		if p > Mlim:
			break
	if Mred > 1:
		dpf += 1
	while dpf < Nlowfac[-1]:
		Nlowfac.pop()
	return Nlowfac[-1]
prs = makePr(32000)
T = int(input())
for tx in range(T):
	(N, M) = map(int, input().split())
	print(get_cols(N, M, prs))


import math

def snek(n):
	z = []
	while n % 2 == 0:
		z.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			z.append(i)
			n = n / i
	if n > 2:
		z.append(n)
	return z
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = len(set(snek(m)))
	c = 0
	while l > 0:
		if n % l == 0:
			c = 1
			break
		else:
			l -= 1
	if c == 1:
		print(l)
	else:
		print(0)


import math

def primeFactors(n):
	pf = []
	while n % 2 == 0:
		pf.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			pf.append(i)
			n = n / i
	if n > 2:
		pf.append(n)
	return pf
for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = len(set(primeFactors(m)))
	x = 0
	while l > 0:
		if n % l == 0:
			x = 1
			break
		else:
			l -= 1
	if x == 1:
		print(l)
	else:
		print(0)


import math

def cntfactors(n):
	cnt = 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			cnt += 1
			while n % i == 0:
				n //= i
		i += 1
	if n != 1:
		cnt += 1
	return cnt

def main():
	t = int(input())
	while t > 0:
		(n, m) = (int(x) for x in input().split())
		factors = cntfactors(m)
		while factors > 1:
			if n % factors == 0:
				break
			factors -= 1
		print(factors)
		t -= 1
main()


import math

def getUniquePrimeFactorsCount(m):
	count = 0
	for i in range(2, int(math.sqrt(m)) + 1):
		if m % i == 0:
			count += 1
			while m % i == 0:
				m = m // i
	if m != 1:
		count += 1
	return count
t = input()
t = int(t)
while t:
	(n, m) = map(int, input().split())
	count = getUniquePrimeFactorsCount(m)
	ans = 0
	for i in range(count, 0, -1):
		if n % i == 0:
			ans = i
			break
	print(ans)
	t -= 1


def GetUniquePrimeCount(n):
	count = 0
	sqrt = int(n ** 0.5) + 1
	for i in range(2, sqrt):
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
	if n > 1:
		count += 1
	return count

def solve():
	(n, m) = map(int, input().split())
	primes = GetUniquePrimeCount(m)
	ans = int()
	for i in range(primes, 0, -1):
		if n % i == 0:
			ans = i
			break
	print(ans)
test_case = int(input())
while test_case:
	solve()
	test_case -= 1


from collections import Counter
from math import ceil, floor, log, gcd, sqrt
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return len(set(l))
for _ in range(int(input().strip())):
	(n, m) = inp_multi()
	temp = primeFactors(m)
	ans = 0
	while temp > 0:
		if n % temp == 0:
			ans = temp
			break
		temp -= 1
	print(ans)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	k = 0
	i = 2
	while i * i < m:
		if m % i == 0:
			while m % i == 0:
				m = m / i
			k += 1
		i += 1
	if m > 1:
		k += 1
	if k == 0:
		print(k)
	else:
		for i in range(k, 0, -1):
			if n % i == 0:
				print(i)
				break


try:
	import math

	def get_prime_factors(n):
		i = 2
		prime_factors = []
		while i * i <= n:
			if n % i == 0:
				prime_factors.append(i)
				n //= i
			else:
				i += 1
		if n > 1:
			prime_factors.append(n)
		return prime_factors
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		z = len(set(get_prime_factors(m)))
		if z == 0:
			print(0)
		else:
			while n % z != 0:
				z -= 1
			print(z)
except:
	pass


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	if m == 1:
		print(0)
	else:
		b = 0
		i = 2
		while i * i <= m:
			c = 0
			while m % i == 0:
				m = m // i
				c = c + 1
			if c:
				b = b + 1
			i = i + 1
		if m != 1:
			b += 1
		for i in range(b, 0, -1):
			if n % i == 0:
				print(i)
				break


t = int(input())
for _t in range(t):
	arr = list(map(int, input().split(' ')))
	(n, m) = (arr[0], arr[1])
	if m == 1:
		print(0)
		continue
	(n_factors, m_prime_factors) = ([], [])
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			n_factors.append(i)
			n_factors.append(n // i)
	for i in range(2, int(m ** 0.5) + 1):
		if m % i == 0:
			m_prime_factors.append(i)
			while m % i == 0:
				m = m // i
	if m >= 2:
		m_prime_factors.append(m)
	answer = 0
	for factor in n_factors:
		if len(m_prime_factors) >= factor:
			answer = max(answer, factor)
	print(answer)


def countPrimeFactors(no):
	factors = set()
	if no == 0 or no == 1:
		return 0
	elif no == 2:
		return 1
	while no % 2 == 0:
		factors.add(2)
		no = no // 2
	for i in range(3, int(no ** 0.5) + 1, 2):
		if no % i == 0:
			factors.add(i)
			while no % i == 0:
				no = no // i
	if no > 2:
		factors.add(no)
	return len(factors)

def maxColumns(col, total_prime):
	ans = 1
	if total_prime == 0:
		return 0
	if col == 1:
		return 1
	while total_prime:
		if col % total_prime == 0:
			ans = total_prime
			return ans
		total_prime -= 1

def main():
	for _ in range(int(input())):
		(col, row) = map(int, input().split())
		total_prime = countPrimeFactors(row)
		ans = maxColumns(col, total_prime)
		print(ans)
main()


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	primes = 0
	(i, primes) = (2, 0)
	while i * i <= m:
		if m % i == 0:
			primes += 1
			while m % i == 0:
				m /= i
		i += 1
	if m != 1:
		primes += 1
	ans = 0
	for i in range(primes, 0, -1):
		if n % i == 0:
			ans = i
			break
	print(ans)


def pf(m):
	(i, c) = (2, 0)
	while i * i <= m:
		if m % i == 0:
			c += 1
			while m % i == 0:
				m = m // i
		i += 1
	return c + 1 if m > 1 else c

def find_factor(n, c):
	i = 1
	l1 = []
	while i * i <= n:
		if n % i == 0:
			l1.append(i)
			l1.append(n // i)
		i += 1
	maxi = 0
	for i in range(len(l1)):
		if l1[i] <= c:
			maxi = max(l1[i], maxi)
	return maxi
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = pf(m)
	if n == 1:
		print(1)
	else:
		print(find_factor(n, c))


import math
for _ in range(int(input())):
	count = 0
	(x, y) = map(int, input().split())
	if y == 1:
		print(0)
		continue
	n = y
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			count += 1
			while n % i == 0:
				n = n / i
	if n != 1:
		count += 1
	if count == 0:
		print(1)
		continue
	while x % count != 0:
		count -= 1
	print(count)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	prime_count = 0
	i = 2
	while i * i <= m:
		if m % i == 0:
			prime_count += 1
			while m % i == 0:
				m /= i
		i += 1
	if m > 1:
		prime_count += 1
	ans = 0
	j = 1
	while j <= prime_count:
		if n % j == 0:
			ans = j
		j += 1
	print(ans)
	t = t - 1


import math
t = int(input())

def prime(x):
	n = x
	if x == 1:
		return 0
	cnt = 0
	i = 2
	while i ** 2 <= n:
		if x % i == 0:
			while x % i == 0:
				x = x // i
			cnt += 1
		i += 1
	if x != 1:
		cnt += 1
	return cnt
for i in range(t):
	(a, b) = list(map(int, input().split()))
	ans = 0
	pfs = prime(b)
	for j in range(pfs, 0, -1):
		if a % j == 0:
			ans = j
			break
	print(ans)


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	temp = m
	i = 2
	while i * i <= m:
		if not temp % i:
			ans += 1
			while not temp % i:
				temp //= i
		i += 1
	if temp > 1:
		ans += 1
	i = 1
	arr = []
	while i * i <= n:
		if not n % i:
			arr.append(i)
			if i != n // i:
				arr.append(n // i)
		i += 1
	a = 0
	for j in arr:
		if j <= ans:
			a = j
	print(a)


import math

def primefactorobtain(N):
	primefactors = []
	while N % 2 == 0:
		primefactors.append(2)
		N = N // 2
	l = math.sqrt(N)
	l = int(l)
	for i in range(3, l + 1, 2):
		while N % i == 0:
			primefactors.append(i)
			N = N // i
	if N > 2:
		primefactors.append(N)
	length = list(set(primefactors))
	return len(length)
T = int(input())
while T > 0:
	(n, m) = map(int, input().split())
	answer = 0
	if m == 1:
		p = 0
	else:
		p = primefactorobtain(m)
		for i in range(p, 0, -1):
			if n % i == 0:
				answer = i
				break
	print(answer)
	T = T - 1


import math
for i in range(int(input())):
	(N, M) = map(int, input().split())
	primeNumbers = []
	while M % 2 == 0:
		if 2 not in primeNumbers:
			primeNumbers.append(2)
		M = M / 2
	for i in range(3, int(math.sqrt(M)) + 1, 2):
		while M % i == 0:
			if i not in primeNumbers:
				primeNumbers.append(i)
			M = M / i
	if M > 2:
		if M not in primeNumbers:
			primeNumbers.append(M)
	numberOfPrimeNumbers = len(primeNumbers)
	if numberOfPrimeNumbers == 0:
		print(0)
	else:
		for i in range(min(N, numberOfPrimeNumbers), 0, -1):
			if N % i == 0:
				if i <= numberOfPrimeNumbers:
					print(i)
					break


import math

def func(n, m):
	x = m
	p = 0
	if m == 1:
		return 0
	for i in range(2, int(math.sqrt(x)) + 1):
		if m % i == 0:
			p += 1
			while m % i == 0:
				m = m // i
	if m > 1:
		p += 1
	for i in range(p, 0, -1):
		if n % i == 0:
			return i
for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	print(func(n, m))


import math
primes = [2, 3]
for i in range(5, int(math.sqrt(10 ** 9)), 2):
	for j in primes[1:]:
		if i % j == 0:
			break
		if j > math.sqrt(i):
			primes.append(i)
			break
t = int(input())
for _ in range(t):
	(c, r) = list(map(int, input().split()))
	if r == 1:
		print(0)
		continue
	pc = 0
	for p in primes:
		if r % p == 0:
			pc += 1
			while r % p == 0:
				r = r // p
		if r == 1:
			break
	if pc == 0:
		print(1)
		continue
	if r > 1:
		pc += 1
	for i in range(pc, 0, -1):
		if c % i == 0:
			ans = i
			break
	print(ans)


t = int(input())
anss = []
for i in range(t):
	(n, m) = list(map(int, input().split()))

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

	def uniq(s):
		uniq = []
		for c in s:
			if c not in uniq:
				uniq.append(c)
		return uniq
	uniqprimefactors = uniq(primeFactors(m))
	if len(uniqprimefactors) == 0:
		anss.append(0)
	for i in range(len(uniqprimefactors), 0, -1):
		if n % i == 0:
			anss.append(i)
			break
for ans in anss:
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m < 2:
		print(0)
	else:
		k = 0
		if m % 2 == 0:
			k += 1
			while m % 2 == 0:
				m = m // 2
		tmp = 3
		m_new = m
		while tmp <= m ** 0.5:
			if m_new % tmp == 0:
				k += 1
				while m_new % tmp == 0:
					m_new //= tmp
			tmp += 2
		if m_new > 1:
			k += 1
		while n % k > 0:
			k -= 1
		print(k)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1:
		print(0)
		continue
	if n == 1:
		print(1)
		continue
	cnt = 0
	for i in range(2, int(math.sqrt(m)) + 1):
		if m % i == 0:
			cnt += 1
			while m % i == 0:
				m //= i
	if m > 1:
		cnt += 1
	div = 0
	for i in range(1, cnt + 1):
		if n % i == 0:
			div = i
	print(div)


import math

def prime(n):
	lst = []
	while n % 2 == 0:
		(lst.append(2),)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			(lst.append(i),)
			n = n / i
	if n > 2:
		lst.append(n)
	return list(set(lst))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1:
		print(0)
		continue
	else:
		a = len(prime(m))
		if a > n:
			print(n)
		elif n % a == 0:
			print(a)
		else:
			while True:
				if n % a == 0:
					print(a)
					break
				else:
					a -= 1


import sys
input = sys.stdin.readline
flush = sys.stdout.flush
get_int = lambda : int(input().rstrip())
get_int_arr = lambda : [int(w) for w in input().split()]
get_str_arr = lambda : input().split()
get_str = lambda : input().rstrip()

def getCountOfPrimeFactors(num):
	count = 0
	probableRange = int(num ** 0.5) + 1
	for i in range(2, probableRange):
		if num % i == 0:
			count += 1
		while num % i == 0:
			num //= i
	if num > 1:
		count += 1
	return count

def solve():
	(base, height) = get_int_arr()
	if height == 1:
		print(0)
		return
	countOfPrimeFactorsOfHeight = getCountOfPrimeFactors(height)
	if countOfPrimeFactorsOfHeight == 0:
		print(1)
	else:
		for i in range(countOfPrimeFactorsOfHeight, 0, -1):
			if base % i == 0:
				print(i)
				break
for _ in range(get_int()):
	solve()


def count_primes(n):
	ans = 0
	if n % 2 == 0:
		ans += 1
	while n % 2 == 0:
		n //= 2
	for i in range(3, int(pow(n, 0.5)) + 1):
		if n % i == 0:
			ans += 1
		while n % i == 0:
			n //= i
	if n > 2:
		ans += 1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	n1 = count_primes(m)
	ans = 0
	for i in range(n1, 0, -1):
		if n % i == 0:
			ans = i
			break
	print(ans)


from sys import stdin, stdout

def is_prime(n):
	var = 1
	if n == 1:
		var = 0
	else:
		for i in range(2, int(pow(n, 0.5)) + 1):
			if n % i == 0:
				var = 0
				break
	return var

def divisor(res):
	set_divisor = set()
	for j in range(1, int(pow(res, 0.5)) + 1):
		if res % j == 0 and is_prime(j):
			set_divisor.add(j)
		if res % j == 0 and is_prime(res // j):
			set_divisor.add(res // j)
	return len(set_divisor)
t = int(stdin.readline().rstrip())
while t > 0:
	(m, n) = map(int, stdin.readline().rstrip().split())
	k = divisor(n)
	if k == 0:
		count = 0
	else:
		count = 0
		for i in range(1, k + 1):
			if m % i == 0:
				if count <= i:
					count = i
	print(count)
	t -= 1


from sys import stdin
input = stdin.readline
from math import sqrt

def primeFac(n):
	if n == 1:
		return 1
	ret = 0
	if n % 2 == 0:
		ret = ret + 1
		while n % 2 == 0:
			n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			ret = ret + 1
			while n % i == 0:
				n = n / i
	if n > 2:
		ret = ret + 1
	return ret

def factors(n, k):
	for i in range(k, 0, -1):
		if n % i == 0:
			return i
	return 0
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1:
		print(0)
		continue
	k = primeFac(m)
	print(factors(n, k))


def primefactors(n):
	net = 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			net += 1
			while n % i == 0:
				n = n // i
		i += 1
	if n != 1:
		net += 1
	return net
t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	x = primefactors(m)
	while x > 0 and n % x != 0:
		x -= 1
	print(x)
	t -= 1


import math

def prime_factors(num):
	s = set()
	while num % 2 == 0:
		s.add(2)
		num = num / 2
	for i in range(3, int(math.sqrt(num)) + 1, 2):
		while num % i == 0:
			s.add(i)
			num = num / i
	if num > 2:
		s.add(num)
	return s
for i in range(int(input())):
	(N, M) = map(int, input().split())
	if N > 1 and M == 1:
		print('0')
	elif N == 1:
		print('1')
	else:
		s = prime_factors(M)
		n = len(s)
		while n > 0 and N % n != 0:
			n -= 1
		print(n)


import math
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	p = 0
	if M == 1:
		print(0)
		continue
	if M % 2 == 0:
		p += 1
		M = M // 2
	while M % 2 == 0:
		M = M // 2
	for i in range(3, int(math.sqrt(M)) + 1, 2):
		if M % i == 0:
			p += 1
		while M % i == 0:
			M = M // i
	if M > 2:
		p += 1
	for i in range(p, 0, -1):
		if N % i == 0:
			print(i)
			break


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	p = 0
	q = b
	i = 2
	while i * i <= b:
		if not q % i:
			p = p + 1
			while not q % i:
				q = q // i
		i = i + 1
	if q > 1:
		p += 1
	l = []
	i = 1
	while i * i <= a:
		if not a % i:
			l.append(i)
			if i != a // i:
				l.append(a // i)
		i = i + 1
	c = 0
	for i in l:
		if i <= p:
			c = i
	print(c)


from collections import Counter

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

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small
for t in range(int(input())):
	(N, M) = map(int, input().split())
	count = len(prime_factors(M))
	while count != 0 and N % count != 0:
		count -= 1
	print(count)


def countPrimeFactors(x):
	count = 0
	i = 2
	while i * i <= x:
		if x % i == 0:
			count += 1
			while x % i == 0:
				x = x // i
		i += 1
	if x != 1:
		count += 1
	return count
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	count = countPrimeFactors(m)
	if count == 0:
		print(0)
	else:
		while True:
			if n % count == 0:
				print(count)
				break
			count -= 1


def numberprimefactors(number):
	i = 0
	count = 0
	for i in range(2, int(number ** 0.5) + 1):
		if number % i == 0:
			count += 1
			while number % i == 0:
				number /= i
	if number != 1:
		count += 1
	return count
numa = int(input())
for x in range(0, numa):
	a1 = input().split()
	a1 = [int(i) for i in a1]
	primecount = numberprimefactors(a1[1])
	while primecount > 0:
		if a1[0] % primecount == 0:
			print(primecount)
			break
		primecount -= 1
	if primecount == 0:
		print('0')


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = 0
	om = m
	if om % 2 == 0:
		a += 1
		while om % 2 == 0:
			om //= 2
	i = 3
	for i in range(3, int(om ** 0.5) + 1, 2):
		if om % i == 0:
			a += 1
		while om % i == 0:
			om //= i
	if om > 1:
		a += 1
	ans = 0
	for i in range(a, 0, -1):
		if n % i == 0:
			ans = i
			break
	print(ans)


import math

def primeFactors(n):
	b = []
	while n % 2 == 0:
		b.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			b.append(i)
			n = n / i
	if n > 2:
		b.append(n)
	return len(set(b))
for i in range(int(input())):
	a = input().split()
	(x, y) = map(int, a)
	if y == 1:
		print(0)
	elif x == 1:
		print(1)
	else:
		n = primeFactors(y)
		if x % n == 0:
			print(n)
		else:
			while n > 0:
				if x % n == 0:
					print(n)
					break
				n -= 1


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	primes = 0
	if m % 2 == 0:
		primes += 1
		while m % 2 == 0:
			m /= 2
	for i in range(3, int(sqrt(m)) + 2, 2):
		if m % i == 0:
			primes += 1
			while m % i == 0:
				m /= i
	if m > 2:
		primes += 1
	ans = 0
	for i in range(primes, 0, -1):
		if n % i == 0:
			ans = i
			break
	print(ans)
print('\n'.join(ANS))


import math
t = int(input())
while t > 0:
	(n, m) = map(int, input().split(' '))
	l = []
	while m % 2 == 0:
		l.append(2)
		m /= 2
	for i in range(3, int(math.sqrt(m)) + 1, 2):
		while m % i == 0:
			l.append(i)
			m /= i
	if m > 2:
		l.append(m)
	p = len(set(l))
	while p > 0:
		if n % p == 0:
			break
		else:
			p -= 1
	print(p)
	t -= 1


from sys import stdin
from math import sqrt
for _ in range(int(stdin.readline())):
	(n, m) = map(int, stdin.readline().split())
	l = []
	while m % 2 == 0:
		l.append(2)
		m = m // 2
	for i in range(3, int(sqrt(m)) + 1, 2):
		while m % i == 0:
			l.append(i)
			m = m // i
	if m > 2:
		l.append(m)
	x = len(set(l))
	if x == 0:
		print(0)
	else:
		while n % x != 0:
			x -= 1
		print(x)


import math

def primeFactors(n):
	ans = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			ans += 1
			while n % i == 0:
				n = n // i
	if n != 1:
		ans += 1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	prime = primeFactors(m)
	if prime >= n:
		print(n)
	else:
		out = 0
		for i in range(prime, 0, -1):
			if n % i == 0:
				out = i
				break
		print(out)


def ChefWM(n, m):
	tot = 0
	primes = 0
	i = 2
	while i * i <= m:
		if m % i == 0:
			primes += 1
			while m % i == 0:
				m //= i
		i += 1
	if m > 1:
		primes += 1
	for i in range(primes, 0, -1):
		if n % i == 0:
			tot = i
			break
	return tot
T = int(input())
for t in range(T):
	(N, M) = input().split()
	(N, M) = (int(N), int(M))
	print(ChefWM(N, M))


from math import sqrt

def getDivisors(n):
	l = []
	add = []
	i = 1
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				l.append(i)
			else:
				l.append(i)
				add.append(n / i)
		i = i + 1
	return l + add[::-1]

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return l
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	if b == 1:
		print(0)
		continue
	if a == 1:
		print(1)
		continue
	ans = len(set(primeFactors(b)))
	for i in range(ans, 0, -1):
		if a % i == 0:
			print(i)
			break


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	temp = m
	i = 2
	while i * i <= m:
		if not temp % i:
			ans += 1
			while not temp % i:
				temp /= i
		i += 1
	if temp > 1:
		ans += 1
	if ans == 0:
		print(ans)
	elif n % ans == 0:
		print(ans)
	else:
		while n % ans != 0:
			ans -= 1
		print(ans)


from math import ceil, gcd, factorial, sqrt, floor, log
import queue
import re
from itertools import permutations, combinations, accumulate
from collections import Counter, deque
from sys import stdin, stdout
from bisect import bisect, insort, bisect_left, insort_left
from types import CodeType
input = lambda : stdin.readline()

def sieve(n):
	prime = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for l1 in range(p * p, n + 1, p):
				prime[l1] = False
		p += 1
	return prime

def simplesieve(n):
	prime = [2]
	mark = [False] * (n + 1)
	for p in range(3, n + 1, 2):
		if mark[p] == False:
			prime.append(p)
			if p * p <= n:
				for l1 in range(p * p, n + 1, 2 * p):
					mark[l1] = True
	return prime

def segementedsieve(low, high):
	primes = simplesieve(int(high ** 0.5))
	prime = [True] * (high - low + 1)
	for l1 in primes:
		lower = low // l1
		if lower <= 1:
			lower = l1 + l1
		elif low % l1 != 0:
			lower = lower * l1 + l1
		else:
			lower = lower * l1
		for l2 in range(lower, high + 1, l1):
			prime[l2 - low] = False
	s1 = []
	s = 0
	for l in range(low, high + 1):
		if prime[l - low]:
			s1.append(l)
	return s1

def isprime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n == 1:
		return False
	for l1 in range(3, int(n ** 0.5) + 1, 2):
		if n % l1 == 0:
			return False
	return True

def binpow(s1, s2, m):
	r2 = 1
	s1 = s1 % m
	while s2 > 0:
		if s2 & 1:
			r2 = r2 * s1 % m
		s1 = s1 * s1 % m
		s2 >>= 1
		print(s1, s2, r2)
	return r2

def lcm(s1, s2):
	return s1 // gcd(s1, s2) * s2

def gcdExtended(s1, s2):
	if s2 == 0:
		return (s1, 1, 0)
	(g, x1, y1) = gcdExtended(s2, s1 % s2)
	l1 = y1
	l2 = x1 - s1 // s2 * y1
	return (g, l1, l2)

def dfs(graph, s, l1):
	v = [0] * (s + 1)
	v[l1] = 1
	s1 = [l1]
	z = 0
	while s1 != []:
		l = s1.pop()
		for l1 in graph[l]:
			if v[l1] == 0:
				v[l1] = 1
				s1.append(l1)
	return 'no'

def bfs(graph, n, x, dest):
	v = [0] * (1 + n)
	d = [0] * (1 + n)
	d[x] = 0
	v[x] = 1
	q = queue.Queue()
	q.put(x)
	while not q.empty():
		z = q.get()
		for s in graph[z]:
			if v[s] == 0:
				v[s] = 1
				d[s] = d[z] + 1
				q.put(s)
	return d[dest]
global iden
iden = [[1, 0], [0, 1]]

def mul(a, b):
	n = len(a)
	ans = []
	for i in range(n):
		r = []
		for j in range(n):
			s = 0
			for k in range(n):
				s += a[i][k] * b[k][j]
			r.append(s)
		ans.append(r)
	return ans

def pow(a, n):
	if n == 0:
		return iden
	k = pow(a, n // 2)
	if n % 2 == 0:
		return mul(k, k)
	return mul(mul(k, k), a)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = m
	c = 0
	for i in range(2, int(m ** 0.5) + 1):
		if k % i == 0:
			c += 1
			while k % i == 0:
				k = k // i
	if k > 1:
		c += 1
	ans = 0
	for i in range(c, 0, -1):
		if n % i == 0:
			ans = i
			break
	print(ans)


from sys import stdin
input = stdin.readline

def count_prime(n):
	i = 2
	count = 0
	while i * i < n:
		if n % i == 0:
			count = count + 1
			while n % i == 0:
				n = n // i
		else:
			i = i + 1
	if n != 1:
		count = count + 1
	return count
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	count = count_prime(m)
	while count:
		if n % count == 0:
			break
		count = count - 1
	print(count)


test = int(input())
while test:
	(n, m) = map(int, input().split())
	ans = 0
	temp = m
	i = 2
	while i * i <= m:
		if not temp % i:
			ans += 1
			while not temp % i:
				temp //= i
		i += 1
	if temp > 1:
		ans += 1
	i = 1
	arr = []
	while i * i <= n:
		if not n % i:
			arr.append(i)
			if i != n // i:
				arr.append(n // i)
		i += 1
	a = 0
	for j in arr:
		if j <= ans:
			a = j
	print(a)
	test -= 1


import sys
f = sys.stdin
next(f)
for s in f:
	(n, m) = map(int, s.split())
	r = c = 0
	i = 2
	while i * i <= m:
		d = 1
		while m % i == 0:
			c += d
			d = 0
			m //= i
		i += 1
	if m > 1:
		c += 1
	i = 1
	while i <= c and i * i <= n:
		if n % i == 0:
			r = n // i
			if r <= c:
				break
			r = i
		i += 1
	print(r)


import math

def primefactors(n):
	lst = []
	while n % 2 == 0:
		(lst.append(2),)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lst.append(i)
			n = n / i
	if n > 2:
		lst.append(int(n))
	return lst
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	le = len(set(primefactors(m)))
	c = 0
	while le > 0:
		if n % le == 0:
			c += 1
			break
		else:
			le -= 1
	if c == 0:
		print(0)
	else:
		print(le)


def factors(n):
	fact = 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			fact += 1
			while n % i == 0:
				n //= i
		i += 1
	if n != 1:
		return fact + 1
	return fact

def maxdivisor(n, m):
	if m == 0:
		return 0
	for i in range(m, 0, -1):
		if n % i == 0:
			return i
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = factors(m)
	print(maxdivisor(n, ans))


t = int(input())

def primefactors(n: int) -> int:
	i = 2
	f = 0
	while i * i < n:
		if n % i == 0:
			f += 1
		while n % i == 0:
			n = n // i
		i += 1
	if n != 1:
		f += 1
	return f
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	max_cols = primefactors(m)
	if max_cols == 0:
		print(0)
		continue
	for i in range(max_cols, 0, -1):
		if n % i == 0:
			print(i)
			break


from sys import *
from math import *
input = stdin.readline
for u in range(int(input())):
	(n, k) = map(int, input().split())
	s = set()
	while k % 2 == 0:
		s.add(2)
		k = k // 2
	for i in range(3, int(sqrt(k)) + 2, 2):
		while k % i == 0:
			s.add(i)
			k = k // i
	if k > 2:
		s.add(k)
	c = len(s)
	f = 0
	while c > 0:
		if n % c == 0:
			f = c
			break
		else:
			c -= 1
	print(f)


import math

def printDivisors(n):
	s = list()
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				s.append(i)
			else:
				s.append(i)
				s.append(n // i)
		i = i + 1
	return sorted(s)[:-1]
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if m == 1:
		print(0)
		continue
	op = printDivisors(m)
	c = 1
	for i in range(len(op) - 2, -1, -1):
		flag = True
		for j in range(i + 1, len(op)):
			if op[j] % op[i] == 0:
				flag = False
				break
		if flag:
			c += 1
	while n % c != 0:
		c -= 1
	print(c)


def rajeev(n):
	ans = 0
	fuck = 1
	while n % 2 == 0:
		n //= 2
		fuck = 2
	if fuck == 2:
		ans += 1
	for r in range(3, int(n ** 0.5) + 1, 2):
		while n % r == 0:
			n //= r
			fuck = r
		if fuck == r:
			ans += 1
	if n > 2:
		ans += 1
	return ans
t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	g = rajeev(m)
	if g >= n:
		print(n)
	elif g == 0:
		print(0)
	else:
		while n % g != 0:
			g -= 1
		print(g)


import math as mt

def primeFactors(num):
	prime = []
	while num % 2 == 0:
		prime.append(2)
		num = num / 2
	for i in range(3, int(mt.sqrt(num)) + 1, 2):
		while num % i == 0:
			prime.append(i)
			num = num / i
	if num > 2:
		prime.append(num)
	return prime
for i in range(int(input())):
	(num, mus) = map(int, input().split())
	lis = len(set(primeFactors(mus)))
	mo = 0
	while lis > 0:
		if num % lis == 0:
			mo = 1
			break
		else:
			lis -= 1
	if mo == 1:
		print(lis)
	else:
		print(0)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	temp = m
	i = 2
	while i * i <= m:
		if not temp % i:
			ans += 1
			while not temp % i:
				temp /= i
		i += 1
	if temp > 1:
		ans += 1
	arr = []
	i = 1
	while i * i <= n:
		if not n % i:
			arr.append(i)
			if i != n // i:
				arr.append(n // i)
		i += 1
	val = 0
	for i in arr:
		if i <= ans:
			val = i
	print(val)


def isPrimeFactor(n):
	count = 0
	if n % 2 == 0:
		count += 1
	while n % 2 == 0:
		n = n // 2
	for i in range(3, int(n ** (1 / 2)) + 1, 2):
		if n % i == 0:
			count += 1
		while n % i == 0:
			n = n // i
	if n > 2:
		count += 1
	return count

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		prime_factors_count = isPrimeFactor(m)
		if prime_factors_count == 0:
			print(0)
			continue
		elif prime_factors_count > n:
			print(n)
		else:
			while n % prime_factors_count != 0:
				prime_factors_count -= 1
			print(prime_factors_count)
main()


def NPrimes(m):
	count = 0
	if m % 2 == 0:
		count += 1
		while m % 2 == 0:
			m = m // 2
	if m % 3 == 0:
		count += 1
		while m % 3 == 0:
			m = m // 3
	i = 5
	while i * i <= m:
		if m % i == 0:
			count += 1
			while m % i == 0:
				m = m // i
		if m % (i + 2) == 0:
			count += 1
			while m % (i + 2) == 0:
				m = m // (i + 2)
		i += 6
	if m > 3:
		count += 1
	return count
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	x = NPrimes(m)
	flag = -1
	if n == 1:
		print(1)
		flag = 0
	else:
		for i in reversed(range(1, x + 1)):
			if n % i == 0:
				flag = 0
				print(i)
				break
	if flag == -1:
		print(0)


import math

def primeFactors(n):
	count = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			count = count + 1
		while n % i == 0:
			n = n / i
	if n > 1:
		count = count + 1
	return count
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	x = primeFactors(m)
	if n < x:
		print(n)
	else:
		f = 0
		while f == 0:
			if x == 0:
				x = 0
				break
			elif n % x == 0 and x != 0:
				f = 1
				break
			else:
				x = x - 1
		print(x)
	t = t - 1


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(2, int(m ** 0.5) + 1):
		if m % i == 0:
			ans += 1
			while m % i == 0:
				m //= i
	if m > 1:
		ans += 1
	p = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			p.append(i)
			p.append(n // i)
	pa = 0
	for i in p:
		if i <= ans:
			pa = i
	print(pa)


import math

def isprime(x):
	y = int(x ** 0.5 + 2)
	if x < 4:
		return True
	for j in range(2, y):
		if x % j == 0:
			return False
	return True

def primeFactors(n):
	seti = set()
	while n % 2 == 0:
		seti.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			seti.add(i)
			n = n // i
	if n > 2:
		seti.add(n)
	return len(seti)
for i in range(int(input())):
	(m, n) = map(int, input().split())
	if n == 1:
		print(0)
	elif m == 1 or isprime(n):
		print(1)
	else:
		temp = primeFactors(n)
		while m % temp != 0:
			temp -= 1
		print(temp)


import math

def primefactors(n):
	lis = []
	while n % 2 == 0:
		lis.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			lis.append(i)
			n = n / i
	if n > 2:
		lis.append(n)
	return lis
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	lis = primefactors(y)
	g = len(set(lis))
	if g == 0:
		print(0)
		continue
	if x % g == 0:
		print(g)
	else:
		while g >= 1:
			if x % g == 0:
				print(g)
				break
			else:
				g -= 1


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = m
	nn = []
	mm = []
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			nn.append(i)
			nn.append(n // i)
	if int(math.sqrt(n)) == math.sqrt(n):
		nn.remove(int(math.sqrt(n)))
	if m % 2 == 0:
		mm.append(2)
		while m % 2 == 0:
			m = m / 2
	for i in range(3, int(math.sqrt(m)) + 1, 2):
		if m % i == 0:
			mm.append(i)
		while m % i == 0:
			m = m / i
	if m > 2:
		mm.append(m)
	b = len(mm)
	ans = [1]
	for hh in nn:
		if hh <= b:
			ans.append(hh)
	if l == 1:
		print(0)
	else:
		print(max(ans))


import math
import os
import random
import re
import sys
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	count = 0
	a = M
	i = 2
	while i * i <= M:
		if a % i == 0:
			count += 1
			while a % i == 0:
				a /= i
		i += 1
	if a > 1:
		count += 1
	b = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			b.append(i)
			if i != int(N / i):
				b.append(int(N / i))
		i += 1
	ans = 0
	for j in range(len(b)):
		if b[j] <= count:
			ans = b[j]
	print(ans)


for k in range(int(input())):
	(N, M) = map(int, input().split())
	answerhai = 0
	tempeory = M
	i = 2
	while i * i <= M:
		if not tempeory % i:
			answerhai += 1
			while not tempeory % i:
				tempeory //= i
		i += 1
	if tempeory > 1:
		answerhai += 1
	A = []
	i = 1
	while i * i <= N:
		if not N % i:
			A.append(i)
			if i != N // i:
				A.append(N // i)
		i += 1
	val = 0
	for i in A:
		if i <= answerhai:
			val = i
	print(val)


import math

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return set(factors)

def divisors(n):
	large_divisors = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			yield i
			if i * i != n:
				large_divisors.append(n / i)
	for divisor in reversed(large_divisors):
		yield int(divisor)
t = input()
for case in range(int(t)):
	(n, m) = [int(c) for c in input().split(' ')]
	mc = len(prime_factors(m))
	for d in divisors(n):
		if n // d <= mc:
			print(n // d)
			break
	else:
		print(0)


from functools import reduce
from sys import stdin, stdout
import math

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

def factors(n):
	step = 2 if n % 2 else 1
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1, step) if n % i == 0)))
t = int(stdin.readline())
for _ in range(t):
	(n, m) = map(int, stdin.readline().split())
	a2 = sorted(factors(m))
	if len(a2) == 1:
		print(0)
	elif len(a2) == 2:
		print(1)
	else:
		a1 = sorted(factors(n))
		a2 = primeFactors(m)
		ab = len(set(a2))
		final = 0
		for x in range(len(a1)):
			if a1[x] <= ab:
				final = a1[x]
		print(final)


import math

def num_div(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def get_prm(n, ver):
	i = 1
	val = 0
	while i * i <= n:
		if n % i == 0:
			if i <= ver:
				val = max(val, i)
			if n // i <= ver:
				val = max(val, n // i)
		i += 1
	return val
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ver = num_div(m)
	if m == 1 and ver < 2:
		print(0)
		continue
	if n == 1:
		print(1)
		continue
	print(get_prm(n, ver))


from collections import defaultdict
import math

def solve(N, M):
	ans = 0
	temp = M
	i = 2
	while i * i <= M:
		if temp % i == 0:
			ans += 1
			while temp % i == 0:
				temp = temp // i
		i += 1
	if temp > 1:
		ans += 1
	dp = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			dp.append(i)
			if i != N // i:
				dp.append(N // i)
		i += 1
	maxx = 0
	for i in dp:
		if i <= ans:
			maxx = i
	return maxx
	pass
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	print(solve(N, M))