The Chef has been hunting for a machine developed to change numbers in a rather peculiar manner. This machine has a fixed number c associated with it and a changing number X. 

In a single step, the Chef can do the following:
First, choose any positive integer b that is a perfect c-th power of some number (that is, there is some positive integer n such that b = n^{c})
Then, change X \to \dfrac{\text{lcm}(b, X)}{\gcd(b, X)}

He wants to find the minimum number he can change X into by applying these operations alone any number of times (possibly none at all). However, he does not know the exact values of X, c for the machine, but he does have T guesses for what these values might be. For each of these guesses, compute the minimum number Chef can obtain.

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

- The first line of input will contain an integer T, the number of guesses Chef has for the pair (X, c). Then the guesses follow.
- Each guess consists of a single line of input containing two space-separated integers X, c.

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

For each guess, print on a new line the minimum value that Chef can change X into by applying any number of operations (possibly none at all).

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

$1 ≤ T ≤ 100$
$1 ≤ X ≤ 10^{10}$
$1 ≤ c ≤ 30$

----- Sample Input 1 ------ 
3
1 5
10 1
20 4
----- Sample Output 1 ------ 
1
1
20
----- explanation 1 ------ 
Guess $1$: It can easily be checked that $X = 1$ cannot be changed.

Guess $2$: Choose $b = 10^{1}$ and change $X : 10 \to \dfrac{\text{lcm}(10, 10)}{\gcd(10, 10)} = 1$. This is the minimum possible value of $X$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import time
import sys
import math
from collections import defaultdict as dd
from functools import lru_cache
inty = lambda : int(input())
stringy = lambda : input().strip()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log(a) / math.log(b)

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
T = inty()
for _ in range(T):
	(x, c) = mappy()
	if x == 1 or c == 1:
		print(1)
		continue
	flag = True
	res = sys.maxsize
	for i in range(1, min(1000, x + 1)):
		temp = i ** c
		res = min(temp * x / gcd(temp, x) ** 2, res)
	print(int(res))


def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def div(x):
	arr = []
	for i in range(1, int(x ** 0.5) + 1):
		if x % i == 0:
			if i * i != x:
				arr.append(i)
				arr.append(x // i)
			else:
				arr.append(i)
	return arr

def cal(x, c, d):
	temp = d ** c
	g = gcd(temp, x)
	x = temp * x // (g * g)
	return x

def mini_x(x, c):
	arr = div(x)
	minx = x
	for ele in arr:
		temp = cal(x, c, ele)
		minx = min(minx, temp)
	return minx
t = int(input())
for tc in range(t):
	(x, c) = map(int, input().split())
	ans = mini_x(x, c)
	print(ans)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def Solution():
	pass

def getPrimeFactor(N):
	factors = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			factors.append(i)
			if i != N // i:
				factors.append(N // i)
		i += 1
	return sorted(factors)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def main():
	lmt = pow(10, 10)
	for _ in range(get_int()):
		(x, c) = get_ints_in_variables()
		if x == 1 or c == 1:
			print(1)
			continue
		while True:
			i = 2
			f = 0
			p = pow(i, c)
			while p < lmt:
				p = pow(i, c)
				tmp = lcm(p, x) // math.gcd(p, x)
				if tmp < x:
					x = tmp
					f = 1
					break
				i += 1
			if f == 0:
				break
		print(x)
main()


T = int(input())
for tx in range(T):
	(X, c) = map(int, input().split())
	if c == 1:
		print(1)
		continue
	f = 2
	elim = c // 2 + 1
	inc = 1
	newX = 1
	while f ** elim <= X:
		if X % f == 0:
			fct = 0
			while X % f == 0:
				fct += 1
				X //= f
			fct %= c
			if fct * 2 > c:
				fct = c - fct
			newX *= f ** fct
		f += inc
		inc = 2
	print(X * newX)


import math

def prinefactors(n):
	prime_factors = []
	for i in range(2, int(math.sqrt(n)) + 1):
		count = 0
		while n % i == 0:
			count += 1
			n /= i
		if count != 0:
			prime_factors.append((i, count))
	if n > 1:
		prime_factors.append((int(n), 1))
	return prime_factors
T = int(input())
for _ in range(T):
	(X, c) = list(map(int, input().split()))
	number = 1
	for j in prinefactors(X):
		val = j[0]
		power = j[1]
		if c - power % c <= power % c:
			number *= val ** (c - power % c)
		else:
			number *= val ** (power % c)
	print(number)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x
z = SieveOfEratosthenes(10 ** 5 + 1)
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	tt = 1
	for i in z:
		p = 0
		while x % i == 0:
			x //= i
			p += 1
		p %= c
		p = min((c - p) % c, p)
		tt *= i ** p
	if x != 1:
		tt *= x
	print(tt)


import math
from collections import defaultdict

def primeFactors(n):
	dic = defaultdict(int)
	while n % 2 == 0:
		dic[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			dic[i] += 1
			n = n / i
	if n > 2:
		dic[n] += 1
	return dic
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	if x == 1 or c == 1:
		print(1)
	else:
		dic = primeFactors(x)
		ans = 1
		for i in dic:
			ans = ans * i ** min(c - dic[i] % c, dic[i] % c)
		print(int(ans))


from math import gcd, pow

def mi(x, c):
	while True:
		f = False
		for l in range(int(pow(x, 1 / c)) + 100, 1, -1):
			k = gcd(l ** c, x)
			if l ** c * x < k ** 2:
				break
			if l ** c * x % k ** 2 == 0:
				if x > l ** c * x // k ** 2:
					f = True
					x = l ** c * x // k ** 2
					break
		if not f:
			break
	return x
for l in range(int(input())):
	(x, c) = [int(a) for a in input().split()]
	print(mi(x, c))


import math

def is_prime(x):
	if x % 2 == 0:
		return False
	sqrtx = math.sqrt(x)
	for i in range(3, int(sqrtx), 2):
		if x % i == 0:
			return False
	return True

def prime_factorization(x):
	factors = []
	if x % 2 == 0:
		factors.append([2, 1])
		x = int(x / 2)
		while x % 2 == 0:
			x = int(x / 2)
			factors[0][1] += 1
	pf = 3
	while x >= pf:
		if is_prime(pf):
			if x < pf ** 2:
				factors.append([x, 1])
				x = 1
			elif x % pf == 0:
				factors.append([pf, 1])
				curr_pos = len(factors) - 1
				x = int(x / pf)
				while x % pf == 0:
					x = int(x / pf)
					factors[curr_pos][1] += 1
		pf += 2
	return factors
t = int(input())
for i in range(t):
	line = input()
	xc = line.split()
	x = int(xc[0])
	c = int(xc[1])
	if x == 1 or c == 1:
		print(1)
	else:
		factors = prime_factorization(x)
		total = 1
		for factor in factors:
			modc = factor[1] % c
			factor[1] = min(modc, c - modc)
			total *= factor[0] ** factor[1]
		print(total)


import math

def primefactors(n):
	prime_factors = []
	for i in range(2, int(math.sqrt(n)) + 1):
		count = 0
		while n % i == 0:
			count += 1
			n = n / i
		if count != 0:
			prime_factors.append((i, count))
	if n > 1:
		prime_factors.append((int(n), 1))
	return prime_factors
for i in range(int(input())):
	(x, c) = map(int, input().split())
	number = 1
	primeFactors = primefactors(x)
	for primeFactor in primeFactors:
		prime = primeFactor[0]
		power = primeFactor[1]
		if c - power % c <= power % c:
			number *= prime ** (c - power % c)
		else:
			number *= prime ** (power % c)
	print(number)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(x, c) = sep()
		d = defaultdict(int)
		for i in range(2, int(math.sqrt(x)) + 2):
			while x % i == 0:
				x //= i
				d[i] += 1
		if x != 1:
			d[x] += 1
		ans = 1
		for i in d:
			res = i ** d[i]
			for j in range(c, 40, c):
				(p, q) = (max(d[i], j), min(d[i], j))
				result = i ** (p - q)
				if result < res:
					res = result
			ans *= res
		print(ans)
main()


import math
import sys

def prime_factors(n):
	res = []
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			count = 0
			while n % i == 0:
				count += 1
				n //= i
			res.append([i, count])
	if n > 1:
		res.append([n, 1])
	return res
t = int(input())
for i in range(t):
	(x, c) = map(int, input().split())
	if x == 1:
		print(1)
		continue
	factor = prime_factors(x)
	ans = 1
	for i in range(len(factor)):
		(a, b) = factor[i]
		b = b % c
		b = min(b, c - b)
		ans *= a ** b
	print(ans)


import math

def primefactors(n):
	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))
t = int(input())
for i in range(t):
	(x, c) = map(int, input().split())
	lst = []
	primefactors(x)
	dic = {}
	for j in lst:
		dic[j] = 0
	for j in lst:
		dic[j] += 1
	ans = {}
	for j in dic.keys():
		ele = dic[j]
		a = ele % c
		b = c - a
		ans[j] = min(a, b)
	ele = 1
	for j in ans.keys():
		a = j ** ans[j]
		ele *= a
	print(ele)


from math import gcd
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	if x == 1 or c == 1:
		print(1)
	else:
		val1 = int(x ** 0.5)
		ans = x
		for i in range(2, val1):
			po = i ** c
			ans = min(ans, po * x // gcd(po, x) ** 2)
		print(ans)


from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
import math
for q in range(int(input())):
	(x, c) = map(int, input().split())
	d = []
	if x == 1 or c == 1 or int(math.exp(math.log(x) / c)) == math.exp(math.log(x) / c):
		print(1)
	else:
		z = factors(x)
		for k in z:
			if k != 1:
				a = k ** c
				g = math.gcd(a, x)
				l = a * x // g
				if l % g == 0:
					d.append(min(x, l // g))
		print(min(d))


from math import gcd
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	if c == 1 or x == 1:
		print(1)
		continue
	least = x
	i = 2
	while i * i <= x:
		if x % i == 0:
			ans = x * i ** c // gcd(x, i ** c) ** 2
			least = min(ans, least)
			ans = x * (x // i) ** c // gcd(x, (x // i) ** c) ** 2
			least = min(ans, least)
		i += 1
		if least == 1:
			break
	print(least)


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())):
	(X, c) = map(int, input().split())
	f = dict(prime_factors(X))
	ans = 1
	for i in f:
		ans *= i ** min(c - f[i] % c, f[i] % c)
	print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	res = 1
	for i in range(2, min(x, 100008)):
		temp = 0
		while x % i == 0:
			x //= i
			temp += 1
		temp %= y
		for j in range(min(y - temp, temp)):
			res *= i
	if y == 1:
		print(1)
	else:
		print(res * x)


import math

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	if c == 1 or x == 1:
		print(1)
	else:
		z = x ** (1 / c)
		z = int(z)
		y = x + 1
		if z != 0:
			for i in range(2, z + 15):
				i = i ** c
				a = x * i // (gcd(x, i) * gcd(x, i))
				y = min(a, y)
		if y > x:
			print(x)
		else:
			print(y)


import math

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	if c == 1 or x == 1:
		print(1)
	else:
		z = math.log(x, 10) / c
		z = 10 ** z
		if int(z) != z:
			z = int(z) + 1
		else:
			z = int(z)
		y = x + 1
		if z != 0:
			for i in range(2, z + 21):
				i = i ** c
				a = y - 1
				while a < y:
					a = x * i // (gcd(x, i) * gcd(x, i))
					y = min(a, y)
		if y > x:
			print(x)
		else:
			print(y)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(X, c) = map(int, input().split())
	if X == 1 or c == 1:
		print(1)
	else:
		i = 2
		ans = X
		for i in range(2, int(X ** (1 / 2))):
			if X % i == 0:
				ans = min(ans, i ** c * X // gcd(X, i ** c) ** 2)
			i += 1
		print(ans)


from math import sqrt
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	p = {}
	v = x
	for i in range(2, int(sqrt(x)) + 1):
		while v % i == 0:
			if i not in p:
				p[i] = 0
			p[i] += 1
			v = v // i
	if v not in p:
		p[v] = 1
	ans = 1
	for el in p:
		ans *= el ** min(p[el] % c, c - p[el] % c)
	print(ans)


import math
from collections import Counter

def func(x, n):
	hcf = math.gcd(x, n)
	lcm = x * n // hcf
	return lcm // hcf

def solve(x, c):
	while x > 1:
		n = 0
		a = 0
		while a <= x:
			n += 1
			a = n ** c
		n -= 1
		m = x
		arr = []
		for i in range(1, 5 * n):
			val = func(x, i ** c)
			arr.append([val, i])
		arr.sort(key=lambda x: (x[0], x[1]))
		m = arr[0][0]
		if m >= x:
			break
		else:
			x = m
	return x
for test in range(int(input())):
	(n, c) = map(int, input().split())
	print(solve(n, c))


import math

def LCM(a, b):
	return int(a * b / math.gcd(a, b))

def find_factors(n):
	factors = []
	i = 1
	while i * i <= n:
		if n % i == 0:
			factors.append(n // i)
			factors.append(i)
		i += 1
	return factors

def scoreFunction(x, y):
	return int(LCM(x, y) / math.gcd(x, y))

def solve(X, c):
	factors = find_factors(X)
	res = [scoreFunction(X, i ** c) for i in factors]
	return min(res)
t = int(input())
for z in range(t):
	(X, c) = map(int, input().split())
	prevAns = solve(X, c)
	if prevAns < X:
		answer = prevAns
		while True:
			nextAns = solve(prevAns, c)
			answer = min(nextAns, answer)
			if nextAns >= prevAns:
				print(answer)
				break
			else:
				prevAns = answer
	else:
		print(X)


import math
import math

def primeFactors(n):
	mp = {}
	while n % 2 == 0:
		if 2 in mp:
			mp[2] += 1
		else:
			mp[2] = 1
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in mp:
				mp[i] += 1
			else:
				mp[i] = 1
			n //= i
	if n > 2:
		mp[n] = 1
	return mp
for _ in range(int(input())):
	(X, c) = map(int, input().split())
	f = primeFactors(X)
	ans = 1
	for v in f:
		f[v] %= c
		f[v] = min(f[v], c - f[v])
		ans *= pow(v, f[v])
	print(ans)


from math import gcd

def gc(a, b):
	return gcd(a, b)

def lc(a, b):
	return a * b // gc(a, b)
try:
	for tc in range(int(input())):
		(x, c) = list(map(int, input().split()))
		if c == 1:
			print(1)
		else:
			r = int(x ** (1 / 2))
			i = r + 1
			while i > 1:
				if x == 1:
					break
				val = i ** c
				g = gc(x, val)
				l = lc(x, val)
				curr = l // g
				if x > curr:
					x = curr
				i -= 1
			print(x)
except EOFError:
	pass


import math
T = int(input())
for ts in range(T):
	(X, c) = map(int, input().split(' '))
	if c == 1:
		print(1)
	else:
		k = 2
		ans = 1
		while k ** (c // 2 + 1) <= X:
			s = 1
			while X % k ** s == 0:
				s = s + 1
			residue = (s - 1) % c
			if residue > c // 2:
				residue = c - residue
			X = X // k ** (s - 1 - residue)
			k = k + 1
		print(X)


import math
from typing import Counter

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(int(n))
	return l

def solve():
	(n, c) = list(map(int, input().split()))
	l = primeFactors(n)
	d = Counter(l)
	ans = 1
	for (i, j) in d.items():
		if j % c != 0:
			ans *= pow(i, min(c - j % c, j % c))
	print(ans)
for _ in range(int(input())):
	solve()


import math

def isprime(n):
	if n < 4:
		return True
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			return False
	return True

def pfactorz(n) -> dict:
	f = {}
	if isprime(n):
		return {n: 1}
	i = 2
	while n > 1:
		while n % i == 0:
			f.setdefault(i, 0)
			f[i] += 1
			n = int(n / i)
		i += 1
	return f

def mindiff(x, c):
	if x > c:
		x %= c
	return min(abs(c - x), x)
t = int(input())
for _ in range(t):
	(x, c) = map(int, input().split())
	if x == 1 or c == 1:
		print(1)
		continue
	if isprime(x):
		print(x)
		continue
	f = pfactorz(x)
	ans = 1
	for (key, val) in f.items():
		md = mindiff(val, c)
		ans = int(ans * math.pow(key, md))
	print(ans)


t = int(input())
for _ in range(t):
	(x, c) = map(int, input().split())
	if c == 1 or x == 1:
		print(1)
		continue
	i = 2
	f = {}
	cx = x
	for i in range(2, 100002):
		if x == 1:
			break
		if x % i == 0:
			if i not in f:
				f[i] = 0
			while x % i == 0:
				x //= i
				f[i] += 1
		i += 1
	ans = 1
	if x > 1:
		f[x] = 1
	for factor in f:
		ans *= max(factor ** min(f[factor] % c, c - f[factor] % c), 1)
	if not f:
		print(cx)
		continue
	print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def func(x, c):
	root = x ** (1 / c)
	root = int(root) + 2
	res = x
	for i in range(root, 0, -1):
		j = i ** c
		g = gcd(res, j)
		res = min(res, res * j // g // g)
	return res
t = int(input())
for _ in range(t):
	(x, c) = map(int, input().split())
	print(func(x, c))


from math import ceil, gcd, sqrt
t = int(input())
while t:
	(x, c) = map(int, input().split(' '))
	if x == 1 or c == 1:
		print(1)
	else:
		mVal = x
		for i in range(2, ceil(sqrt(x)) + 1):
			if x % i == 0:
				temp = i ** c
				mVal = min(mVal, x * temp // (gcd(x, temp) * gcd(x, temp)))
		print(mVal)
	t -= 1


def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
mod = 10 ** 4

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	ans = []
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def nextPowerOf2(n):
	count = 0
	if n and (not n & n - 1):
		return n
	while n != 0:
		n >>= 1
		count += 1
	return 1 << count
from collections import defaultdict
import math

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

def upper_bound(arr, target):
	start = 0
	end = len(arr) - 1
	ans = -1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] <= target:
			start = mid + 1
		else:
			ans = mid
			end = mid - 1
	return ans

def get_dis(s1, s2):
	s = 'abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
	a1 = s.index(s1)
	a2 = s.rfind(s1)
	b1 = s.index(s2)
	b2 = s.rfind(s2)
	return min(abs(a1 - b1), abs(a1 - b2), abs(a2 - b1), abs(a2 - b2))
from collections import defaultdict

def func(l, m):
	ans = 0
	s = set()
	for ele in l:
		ans += ele % m
		print(ans, ele % m, ele, m)
		if ele % m in s:
			return -1
	print('tot', len(l) * (len(l) + 1) // 2, ans)
	if ans == len(l) * (len(l) + 1) // 2:
		return 1
	return 0

def printDivisors(n):
	i = 1
	res = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				res.append(i)
			else:
				res.append(i)
				res.append(n // i)
		i = i + 1
	return res

def func(x):
	c = 0
	while x != 0 and x % 2 == 0:
		x = x // 2
		c += 1
	return c
INF = 1000000000000000000000
from collections import deque

def solve():
	d = defaultdict(int)
	(n, k) = list(map(int, input().split()))
	lis = primeFactors(n)
	for ele in lis:
		d[ele] += 1
	ans = 1
	st = set()
	for (ke, v) in d.items():
		y = ke ** k
		x = n
		x = x * y // (math.gcd(x, y) * math.gcd(x, y))
		while x < n:
			n = x
			y = ke ** k
			x = n
			x = x * y // (math.gcd(x, y) * math.gcd(x, y))
	print(n)
num_test = 1
num_test = int(input())
for _ in range(num_test):
	solve()


import sys

def L():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def I():
	return int(sys.stdin.readline())

def M():
	return map(int, sys.stdin.readline().rstrip().split())
from math import gcd

def gcd_val(a, b):
	return gcd(a, b)

def lcm_val(a, b):
	return a * b // gcd(a, b)
for _ in range(int(input())):
	(x, c) = M()
	if c == 1:
		print(1)
	else:
		r = int(x ** (1 / 2))
		i = r + 1
		while i > 1:
			if x == 1:
				break
			gcm = gcd_val(x, i ** c)
			lcm = lcm_val(x, i ** c)
			x = min(x, lcm // gcm)
			i -= 1
		print(x)


import math
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	if c == 1 or x == 1:
		print(1)
		continue
	dit = {}
	n = x
	for i in range(2, int(math.sqrt(n)) + 2):
		if n % i == 0:
			dit[i] = 1
			n = n // i
			while n % i == 0:
				n = n // i
				dit[i] += 1
	if n > 1:
		dit[n] = 1
	for e in dit:
		while dit[e] >= c // 2 + 1:
			if dit[e] >= c:
				dit[e] -= c
			else:
				dit[e] = c - dit[e]
	ans1 = 1
	for e in dit:
		ans1 *= e ** dit[e]
	print(ans1)


import math
for _ in range(int(input())):
	(x, c) = map(int, input().split())
	a = set()
	for i in range(1, int(x ** 0.5) + 1):
		if x % i == 0:
			a.add(i)
			a.add(x // i)
	b = x
	for i in a:
		b = min(b, x * i ** c // math.gcd(x, i ** c) ** 2)
	print(b)


from math import gcd
try:
	for tc in range(int(input())):
		(x, c) = list(map(int, input().split()))
		if c == 1:
			print(1)
		else:
			r = int(x ** (1 / 2))
			i = r + 1
			while i > 1:
				if x == 1:
					break
				gcm = gcd(x, i ** c)
				lcm = x * i ** c // gcm
				x = min(x, lcm // gcm)
				i -= 1
			print(x)
except EOFError:
	pass


from math import gcd
try:
	for tc in range(int(input())):
		(x, c) = list(map(int, input().split()))
		if c == 1:
			print(1)
		else:
			r = int(x ** (1 / 2))
			for i in range(r + 1, 1, -1):
				if x == 1:
					break
				gc = gcd(x, i ** c)
				lc = x * i ** c // gc
				x = min(x, lc // gc)
			print(x)
except EOFError:
	pass


import math
t = int(input())
prime = [True for i in range(10 ** 6 + 10 + 1)]
p = []

def SieveOfEratosthenes(n):
	r = 2
	while r * r <= n:
		if prime[r] == True:
			for i in range(r * r, n + 1, r):
				prime[i] = False
		r += 1
	for r in range(2, n + 1):
		if prime[r]:
			p.append(r)
SieveOfEratosthenes(10 ** 6 + 10)
while t > 0:
	a = input().split()
	(x, c) = (int(a[0]), int(a[1]))
	ans = 1
	n = len(p)
	for i in range(n):
		cur = 0
		while x % p[i] == 0:
			cur += 1
			x = x // p[i]
		cur = cur % c
		if cur > 0:
			g = math.gcd(c, cur)
			g = min(cur, c - cur)
			ans = ans * p[i] ** g
	print(ans * x)
	t -= 1


import math
for j in range(int(input())):
	(x, c) = map(int, input().split())
	l = []
	i = 1
	while i <= math.sqrt(x):
		if x % i == 0:
			if x / i == i:
				l.append(i)
			else:
				l.extend([i, x // i])
		i = i + 1
	l.sort()
	mi = x
	for i in l:
		g = math.gcd(x, i ** c)
		mi = min(mi, i ** c * x // g // g)
	print(mi)


from bisect import bisect_left
from re import sub
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys

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

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
			else:
				c += 2
		i += 1
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(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 len(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

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

def solve():
	(x, c) = map(int, input().split())
	d = primeFactors(x)
	for ele in d:
		k = d[ele]
		while k > k + c - 2 * min(k, c):
			k = k + c - 2 * min(k, c)
			d[ele] = k
	ans = 1
	for ele in d:
		ans *= ele ** d[ele]
	print(ans)
for _ in range(int(input())):
	solve()


from math import gcd, log, ceil
for _ in range(int(input())):
	(X, c) = map(int, input().split())
	if c == 1 or X == 1:
		print(1)
	else:
		n = ceil(pow(X, 1 / c)) + 1
		b = pow(n, c)
		while n > 1:
			t = X * b // pow(gcd(X, b), 2)
			if t < X:
				X = t
				n += 1
			n -= 1
			b = pow(n, c)
		print(X)


import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a // gcd(a, b) * b
t = int(input())
for _ in range(t):
	(x, c) = map(int, input().split())
	i = 1
	temp = x
	ans = 10 ** 291
	while i * i <= x:
		if x % i == 0:
			j = x // i
			g1 = gcd(x, i ** c)
			g2 = gcd(x, j ** c)
			l1 = lcm(x, i ** c)
			l2 = lcm(x, j ** c)
			ans = min(ans, l1 // g1)
			ans = min(ans, l2 // g2)
		i = i + 1
	print(ans)


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

def main():
	(x, c) = map(int, input().split())
	if c == 1 or x == 1:
		return 1
	dec = PrimeFact(x)
	ans = 1
	for (k, v) in dec.items():
		cnt = v % c
		dec[k] = min(cnt, c - cnt)
		ans *= pow(k, dec[k])
	return ans
for _ in range(int(input())):
	print(main())


import math

def power(x, y):
	res = 1
	while y > 0:
		if y & 1 != 0:
			res = res * x
		y = y >> 1
		x = x * x
	return res
t = int(input())
while t:
	(x, c) = [int(x) for x in input().split()]
	if c == 1:
		print(1)
	else:
		ans = int(10000000000.0 + 1)
		for i in range(1, 1000):
			den = math.gcd(x, power(i, c))
			den = den * den
			num = x * power(i, c)
			temp = num // den
			if temp < ans:
				ans = temp
		print(ans)
	t = t - 1


from collections import Counter
import math

def primeFactors(n):
	arr = []
	while n % 2 == 0:
		arr.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			arr.append(i)
			n = n / i
	if n > 2:
		arr.append(int(n))
	return arr
tc = int(input())
for _ in range(tc):
	(x, c) = map(int, input().split())
	factors = Counter(primeFactors(x))
	ans = 1
	for i in factors:
		cur = factors[i]
		cur %= c
		cur = min(cur, c - cur)
		ans *= i ** cur
	print(ans)


import sys
from math import sqrt, gcd, factorial, ceil, floor
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007

def solver(n):
	while n % 2 == 0:
		if 2 not in d:
			d[2] = 0
		d[2] += 1
		n //= 2
	for i in range(3, int(sqrt(n) + 1), 2):
		if i not in d:
			d[i] = 0
		while n % i == 0:
			d[i] += 1
			n //= i
	if n > 2:
		d[n] = 1
for _ in range(I()):
	d = {}
	(x, c) = M()
	solver(x)
	ans = 1
	for i in d:
		ans *= i ** min(c - d[i] % c, d[i] % c)
	print(ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from queue import PriorityQueue
from queue import Queue
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
import random
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def hnbhai(tc):
	(n, c) = sd()
	d = {}
	x = 2
	while x * x <= n:
		cnt = 0
		while n % x == 0:
			n //= x
			cnt += 1
		d[x] = cnt
		x += 1
	if n > 1:
		d[n] = 1
	ans = 1
	for i in d:
		ans *= i ** min(c - d[i] % c, d[i] % c)
	print(ans)
	return
for _ in range(sb()):
	hnbhai(_ + 1)