You are given an integer N. Let K be a divisor of N of your choice such that K > 1, and let M = \frac{N}{K}. You need to find the smallest K such that M has as many divisors as possible.

Note: U is a divisor of V if V is divisible by U.

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

- The first line of the input contains an integer T - the number of test cases. The test cases then follow.
- The only line of each test case contains an integer N.

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

For each test case, output in a single line minimum value of K such that M has as many divisors as possible.

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

$1 ≤ T ≤ 3000$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
3
4
6

----- Sample Output 1 ------ 
3
2
2

----- explanation 1 ------ 
- Test case $1$: The only possible value for $K$ is $3$, and that is the answer.
- Test case $2$: There are two cases:
- $K = 2$. Then $M = \frac{4}{2} = 2$, which has $2$ divisors ($1$ and $2$).
- $K = 4$. Then $M = \frac{4}{4} = 1$, which has $1$ divisor ($1$).

Therefore the answer is $2$.
- Test case $3$: There are three cases:
- $K = 2$. Then $M = \frac{6}{2} = 3$, which has $2$ divisors ($1$ and $3$).
- $K = 3$. Then $M = \frac{6}{3} = 2$, which has $2$ divisors ($1$ and $2$).
- $K = 6$. Then $M = \frac{6}{6} = 1$, which has $1$ divisor ($1$).

Therefore the answer is $2$.

Difficulty: HARD
Tags: Number theory

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from math import sqrt
MAX = int(sqrt(10 ** 9) + 1e-05)
pa = [True] * MAX
i = 2
while i * i <= MAX:
	if pa[i - 1]:
		j = i * i
		while j <= MAX:
			pa[j - 1] = False
			j += i
	i += 1
pr = [num for num in range(2, MAX) if pa[num - 1]]
for _ in range(int(input())):
	N = int(input())
	nmb = N
	me = 0
	res = 0
	for p in pr:
		e = 0
		while nmb % p == 0:
			nmb //= p
			e += 1
		if e > me:
			res = p
			me = e
	if me == 0:
		res = N
	print(res)


def solve():
	n = int(input())
	i = 2
	(maxfreq, v) = (0, -1)
	while i * i <= n:
		count = 0
		while n % i == 0:
			count += 1
			n //= i
		if count > maxfreq:
			maxfreq = count
			v = i
		i += 1
	if maxfreq:
		return v
	return n
t = int(input())
while t:
	print(solve())
	t -= 1


def solve():
	n = int(input())
	i = 2
	factors = []
	while i * i <= n:
		count = 0
		while n % i == 0:
			count += 1
			n //= i
		if count:
			factors.append([-count, i])
		i += 1
	if factors:
		factors.sort()
		return factors[0][1]
	return n
t = int(input())
while t:
	print(solve())
	t -= 1


import math
mx = math.ceil(math.sqrt(10 ** 9))
primes = []
prime = [True] * mx
for i in range(2, mx):
	if prime[i]:
		primes.append(i)
		for i in range(i ** 2, mx, i):
			prime[i] = False
for _ in range(int(input())):
	N = int(input())
	mx = 0
	val = N
	for i in primes:
		if i * i > N:
			break
		if N % i == 0:
			j = 1
			while not N % i ** j:
				j += 1
			if j > mx:
				mx = j
				val = i
	print(val)


import math
pf = []

def pfe(x, l):
	for i in range(l, math.floor(math.sqrt(x)) + 2):
		if x % i == 0:
			pf.append(i)
			pfe(x // i, i)
			return
	if x > 1:
		pf.append(x)
for tea in [0] * int(input()):
	n = int(input())
	pf = []
	pfe(n, 2)
	lol = dict()
	for i in pf:
		if i in lol:
			lol[i] += 1
		else:
			lol[i] = 1
	maxx = -1
	deMax = -1
	for i in sorted(list(lol)):
		if lol[i] > maxx:
			maxx = lol[i]
			deMax = i
	print(deMax)


t = int(input())
for _ in range(t):
	n = int(input())
	i = 2
	M = 0
	while i * i <= n:
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n //= i
				cnt += 1
			if cnt > M:
				M = cnt
				ans = i
		i += 1
	if n > 1 and M == 0:
		ans = n
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	ans = n
	maxp = 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			p = 0
			while n % i == 0:
				p += 1
				n = n // i
			if p > maxp:
				maxp = p
				ans = i
		i += 1
	print(ans)


def func(n):
	mp = 0
	no = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			temp = n
			p = 0
			while n % i == 0:
				n = n // i
				p += 1
			if mp < p:
				mp = p
				no = i
		i += 1
	return no
t = int(input())
for _ in range(t):
	n = int(input())
	print(func(n))


for _ in range(int(input())):
	n = int(input())
	i = 2
	res = n
	mxp = 0
	while i * i <= n:
		if n % i == 0:
			powr = 0
			while n % i == 0:
				n = n // i
				powr += 1
			if powr > mxp:
				mxp = powr
				res = i
		i += 1
	print(res)


from sys import stdin
from math import sqrt

def check(n):
	dic = {2: 0}
	while n % 2 == 0:
		dic[2] += 1
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			if i not in dic.keys():
				dic[i] = 1
			else:
				dic[i] += 1
			n = n / i
	if n > 2:
		dic[n] = 1
	(key, mx) = (0, 0)
	for i in dic.keys():
		if dic[i] > mx:
			key = i
			mx = dic[i]
	return int(key)
t = int(input())
for _ in range(t):
	n = int(input())
	print(check(n))


from math import ceil, log, floor, sqrt, gcd
for _ in range(int(input())):
	n = int(input())
	ans = 0
	pcnt = 0
	cnt = 0
	while n % 2 == 0:
		cnt += 1
		n = n / 2
	if cnt > 0:
		pcnt = cnt
		ans = 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		cnt = 0
		if n % i == 0:
			while n % i == 0:
				cnt += 1
				n = n / i
			if cnt > pcnt:
				pcnt = cnt
				ans = i
	if ans == 0:
		ans = n
	print(ans)


import math
for _ in range(int(input())):

	def func(x):
		return d[x]
	N = int(input())
	d = {}
	while N % 2 == 0:
		if 2 in d:
			d[2] += 1
		else:
			d[2] = 1
		N = N // 2
	for i in range(3, int(math.sqrt(N)) + 1, 2):
		while N % i == 0:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			N = N // i
		if N == 1:
			break
	if N > 2:
		d[N] = 1
	a = sorted(d, key=func, reverse=True)
	print(a[0])


from collections import Counter

def get_prime_number(n):
	i = 2
	prime_number = []
	while i * i <= n:
		if n % i == 0:
			prime_number.append(i)
			n //= i
		else:
			i += 1
	if n > 1:
		prime_number.append(n)
	return prime_number
for _ in range(int(input())):
	n = int(input())
	arr = get_prime_number(n)
	d = Counter(arr)
	key = list(d.keys())
	value = list(d.values())
	print(key[value.index(max(value))])


import math
from collections import Counter

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(n)
	cnt = Counter(arr)
	vmax = max(cnt.values())
	for (k, v) in cnt.items():
		if v == vmax:
			return k
T = int(input())
for tc in range(T):
	n = int(input())
	print(primeFactors(n))


import math
for i in range(int(input())):
	dic = {2: 0}
	n = int(input())
	while n % 2 == 0:
		n = n / 2
		dic[2] += 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			n = n / i
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
	if n > 2:
		dic[n] = 1
	(maxx, key) = (0, 0)
	for i in dic.keys():
		if dic[i] > maxx:
			maxx = dic[i]
			key = i
	print(key)


import math

def primeFactors(n):
	u = []
	maxi = 0
	r = 0
	find = 0
	while n % 2 == 0:
		(u.append(2),)
		n = n / 2
		r = r + 1
		if r > maxi:
			maxi = r
			find = 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		r = 0
		while n % i == 0:
			u.append(i)
			n = n / i
			r = r + 1
		if r > maxi:
			maxi = r
			find = i
	r = 0
	if n > 2:
		u.append(n)
		r = r + 1
		if r > maxi:
			maxi = r
			find = n
	return find
m = int(input())
for i in range(0, m):
	t = int(input())
	v = primeFactors(t)
	print(v)


import math
for i in range(int(input())):
	n = int(input())
	dictt = {2: 0}
	while n % 2 == 0:
		n = n / 2
		dictt[2] += 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			n = n / i
			if i in list(dictt.keys()):
				dictt[i] += 1
			else:
				dictt[i] = 1
	if n > 2:
		dictt[n] = 1
	maxx = 0
	pf = 0
	for i in list(dictt.keys()):
		if dictt[i] > maxx:
			maxx = dictt[i]
			pf = i
	print(pf)


import math
t = int(input())
while t > 0:
	n = int(input())
	cnt = 0
	l = []
	while n % 2 == 0:
		cnt += 1
		n = n // 2
	l.append((2, cnt))
	for p in range(3, int(math.sqrt(n)) + 1, 2):
		if n % p == 0:
			cnt = 0
			while n % p == 0:
				n = n // p
				cnt += 1
			l.append((p, cnt))
	if n > 2:
		l.append((n, 1))
	print(l[l.index(max(l, key=lambda x: x[1]))][0])
	t -= 1


try:
	from collections import Counter
	import math

	def primeFactors(n):
		gl = []
		while n % 2 == 0:
			gl.append(2)
			n = n / 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				gl.append(i)
				n = n / i
		if n > 2:
			gl.append(n)
		return gl
	for _ in range(int(input())):
		n = int(input())
		cc = primeFactors(n)
		c = list(Counter(cc).most_common())
		print(c[0][0])
except:
	pass


import heapq
import math
import sys
import collections
import bisect
import time
import random
import itertools
import string
from collections import Counter, defaultdict

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

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

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

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n // i
	if n > 2:
		ans.append(n)
	return ans
for t in range(int(input())):
	n = int(input())
	pf = primeFactors(n)
	counter = collections.Counter(pf)
	val = max(counter.values())
	ans = 10 ** 10
	for i in counter:
		if counter[i] == val:
			ans = min(ans, i)
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	i = 2
	while i * i <= n:
		while n % i == 0:
			d[i] += 1
			n //= i
		i += 1
	if n > 1:
		d[n] = 1
	print(-max(((v, -k) for (k, v) in d.items()))[1])


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	div = defaultdict(lambda : 0)
	while n % 2 == 0:
		div[2] += 1
		n /= 2
		p = False
	i = 3
	while i * i <= n:
		while n % i == 0:
			div[i] += 1
			n /= i
		i += 2
	if n > 2:
		div[n] += 1
	print(max(div, key=lambda x: div[x]))


def countDivisors(n):
	cnt = 0
	ans = 0
	curr = 0
	while n % 2 == 0:
		n //= 2
		cnt += 1
	if cnt > curr:
		ans = 2
		curr = cnt
	i = 3
	while i * i <= n:
		cnt = 0
		while n % i == 0:
			n //= i
			cnt += 1
		if cnt > curr:
			ans = i
			curr = cnt
		i += 2
	if n > 1:
		if 1 > curr:
			ans = n
			curr = 1
	return ans
for _ in range(int(input())):
	n = int(input())
	print(countDivisors(n))


import math

def countDivisors(n):
	dic = dict()
	while n % 2 == 0:
		if 2 not in dic:
			dic[2] = 0
		dic[2] += 1
		print
		(2,)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i not in dic:
				dic[i] = 0
			dic[i] += 1
			n = n // i
	if n > 2:
		if n not in dic:
			dic[n] = 0
		dic[n] += 1
	return dic
for t in range(int(input())):
	N = int(input())
	count = countDivisors(N)
	maxCount = max(count.values())
	arr = []
	for i in count.keys():
		if count.get(i) == maxCount:
			arr.append(i)
	print(min(arr))


import math
for _ in range(int(input())):
	n = int(input())
	ans = n
	lc = 1
	a2 = 1
	while n % 2 == 0:
		lc += 1
		n = n // 2
	if lc > a2:
		a2 = lc
		ans = 2
	end = int(n ** 0.5)
	for i in range(3, math.ceil(math.sqrt(n)) + 1, 2):
		lc = 1
		if n % i == 0:
			while n % i == 0:
				lc += 1
				n = n // i
			if lc > a2:
				a2 = lc
				ans = i
	print(ans)


import math
from collections import defaultdict
import math

def primeFactors(n):
	d = defaultdict(int)
	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[i] += 1
			n = n / i
	if n > 2:
		d[n] += 1
	return d
for _ in range(int(input())):
	n = int(input())
	d = primeFactors(n)
	maxi = max(d.values())
	for i in sorted(d.keys()):
		if d[i] == maxi:
			print(i)
			break


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

def primeFactor(n):
	d = {}
	while n % 2 == 0:
		if 2 not in d:
			d[2] = 1
		else:
			d[2] += 1
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0 and n:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
			n //= i
	if len(d) == 0:
		print(n)
	else:
		print(max(d, key=d.get))
for _ in range(int(input())):
	n = int(input())
	k = 0
	primeFactor(n)


def minPrimeDiv(n):
	mx = 0
	minPrime = 1000000007
	i = 2
	y = n
	while i * i <= y:
		nof = 0
		while y % i == 0:
			nof += 1
			y = y // i
		if mx < nof:
			mx = nof
			minPrime = i
		i += 1
	if mx == 0:
		return n
	else:
		return minPrime
t = int(input())
for tc in range(t):
	n = int(input())
	print(minPrimeDiv(n))


import math

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		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
t = int(input())
while t:
	t -= 1
	x = int(input())
	l = primeFactors(x)
	l1 = []
	lf = []
	ans = 0
	cnt = 0
	for i in l:
		if i not in l1:
			l1.append(i)
	for i in range(len(l1)):
		x = l1[i]
		if l.count(x) > cnt:
			cnt = l.count(x)
			ans = x
	print(int(ans))


from math import ceil, gcd, factorial, sqrt, floor
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
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):
	limit = int(sqrt(high))
	primes = simplesieve(limit)
	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, s):
	r2 = 1
	s1 = s1 % s
	while s2 > 0:
		if s2 & 1:
			r2 = r2 * s1 % s
		s1 = s1 * s1 % s
		s2 >>= 1
	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]
prime = simplesieve(31623)
for _ in range(int(input())):
	n = int(input())
	k = n
	m = 0
	ans = n
	for i in prime:
		if i > k:
			break
		if k % i == 0:
			c = 0
			while k % i == 0:
				c += 1
				k = k // i
			if m < c:
				m = c
				ans = i
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	d = {}
	i = 2
	while i * i <= n:
		if n % i == 0:
			n = n // i
			if i not in d:
				d[i] = 0
			d[i] += 1
		else:
			i = i + 1
	if n not in d:
		d[n] = 0
	d[n] += 1
	mx = max(d.values())
	a = list(d.keys())
	for i in range(len(a)):
		if d[a[i]] == mx:
			break
	print(a[i])


import math

def primeFactors(n):
	dic = {2: 0}
	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:
			if i not in dic.keys():
				dic[i] = 1
			else:
				dic[i] += 1
			n = n / i
	if n > 2:
		dic[n] = 1
	(key, max) = (0, 0)
	for i in dic.keys():
		if dic[i] > max:
			key = i
			max = dic[i]
	print(key)
for _ in range(int(input())):
	n = int(input())
	primeFactors(n)


def prime_factors(n):
	(i, factors) = (2, [])
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return list(set(factors))
t = int(input())
for _ in range(t):
	n = int(input())
	primes = prime_factors(n)
	count = []
	for prime in primes:
		k = n
		counter = 0
		while k % prime == 0:
			counter += 1
			k = k // prime
		count.append(counter)
	check2 = -1
	check1 = []
	max_occur = 0
	for i in range(len(primes)):
		if count[i] > 1:
			if max_occur == 0:
				check2 = primes[i]
				max_occur = count[i]
			elif count[i] > max_occur:
				check2 = primes[i]
				max_occur = count[i]
			elif count[i] == max_occur:
				check2 = min(check2, primes[i])
		else:
			check1.append(primes[i])
	if check2 == -1:
		ans = min(check1)
	else:
		ans = check2
	print(ans)


import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	if not n & 1:
		while n % 2 == 0:
			d[2] += 1
			n //= 2
	if n != 1:
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				d[i] += 1
				n //= i
			if n == 1:
				break
		else:
			d[n] = 1
	print(max(d, key=lambda x: d[x]))


from collections import defaultdict
import math

def solve(N):
	d = defaultdict(int)
	while N % 2 == 0:
		d[2] += 1
		N //= 2
	i = 0
	for i in range(3, int(math.sqrt(N)) + 1, 2):
		while N % i == 0:
			d[i] += 1
			N = N // i
	if N > 2:
		d[N] += 1
	return d
	pass
T = int(input())
for i in range(T):
	N = int(input())
	d = solve(N)
	maxi = max(d.values())
	for i in sorted(d.keys()):
		if d[i] == maxi:
			print(i)
			break


from math import sqrt
t = int(input())

def func(n: int):
	divs = dict()
	while n % 2 == 0:
		try:
			divs[2] += 1
		except:
			divs[2] = 1
		n /= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			try:
				divs[i] += 1
			except:
				divs[i] = 1
			n /= i
	if n > 1:
		divs[n] = 1
	max_freq = 0
	for divisor in divs:
		freq = divs[divisor]
		if freq > max_freq:
			max_freq = freq
	for (divisor, freq) in divs.items():
		if freq == max_freq:
			return divisor
while t > 0:
	n = int(input())
	print(func(n))
	t -= 1


from collections import defaultdict as dd, Counter as C
for _ in range(int(input())):
	n = int(input())
	D = dd(int)
	flag = 0
	while n % 2 == 0:
		D[2] += 1
		n //= 2
		flag = 1
	i = 3
	while i * i <= n:
		while n % i == 0:
			D[i] += 1
			n //= i
			flag = 1
		i += 2
	if flag == 0:
		print(n)
	else:
		cc = C(D)
		print(cc.most_common(1)[0][0])


from math import sqrt

def prime(x):
	if x == 2:
		return True
	else:
		for i in range(2, int(sqrt(x)) + 1):
			if x % i == 0:
				return False
		return True

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

def finddd(x):
	maxx = 0
	anss = x
	while x % 2 == 0:
		maxx += 1
		x /= 2
		anss = 2
	for i in range(3, int(sqrt(x)) + 1, 2):
		cnt = 0
		while x % i == 0:
			cnt += 1
			x /= i
		if cnt > maxx:
			maxx = cnt
			anss = i
	if x > 2:
		if 1 > maxx:
			maxx = 1
			anss = x
	return anss
for _ in range(int(input())):
	x = int(input())
	if x <= 3:
		print(x)
	else:
		print(finddd(x))


import math

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
v = simplesieve(10 ** 5 + 1)

def nDivisors(n):
	t = 0
	m = -1
	for i in v:
		if n % i == 0:
			lol = 0
			while n % i == 0:
				lol += 1
				n = n // i
			if t < lol:
				t = lol
				m = i
	if n != 1:
		if m < 1:
			return n
	return m
for _ in range(int(input())):
	n = int(input())
	print(nDivisors(n))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
maxN = 100010
dp = [i for i in range(maxN + 1)]
size = 0
prime = []
i = 2
for i in range(2, maxN + 1):
	if dp[i] == i:
		prime.append(i)
		size += 1
	j = 0
	while j < size and i * prime[j] <= maxN and (dp[i * prime[j]] >= prime[j]):
		dp[i * prime[j]] = prime[j]
		j += 1

def solve():
	n = inp()
	MA = 0
	i = 0
	ans = -1
	for i in prime:
		if n % i == 0:
			c = 0
			while n % i == 0:
				n //= i
				c += 1
			if c > MA:
				MA = c
				ans = i
	if n != 1:
		if MA < 1:
			ans = n
	pr(ans)
for _ in range(inp()):
	solve()


from collections import defaultdict
import math
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	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[i] += 1
			n = n // i
	if n > 2:
		d[n] += 1
	ans = -1
	maxi = 0
	for (k, v) in d.items():
		if v > maxi:
			ans = k
			maxi = v
		if v == maxi:
			ans = min(ans, k)
	print(ans)


import math
from collections import Counter

def prime(n):
	d = Counter()
	while n % 2 == 0:
		d[2] = d.get(2, 0) + 1
		n = n // 2
	for i in range(3, math.ceil(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] = d.get(i, 0) + 1
			n = n // i
	if n > 2:
		d[n] = d.get(n, 0) + 1
	return d
for _ in range(int(input())):
	n = int(input())
	res = prime(n)
	print(res.most_common()[0][0])


class Solution:

	def __init__(self):
		self.prime = []
		self.d = {}

	def pre(self):
		for i in range(2, 10 ** 5):
			if i not in self.d:
				self.prime.append(i)
				for j in range(i * 2, 10 ** 5, i):
					self.d[j] = 1
s = Solution()
s.pre()
t = int(input())
for i in range(t):
	n = int(input())
	done = 0
	one = 0
	d = {}
	ncopy = n
	for j in s.prime:
		if n % j == 0:
			d[j] = 0
			while n % j == 0:
				n = n // j
				d[j] += 1
	if len(d) == 0:
		print(ncopy)
		continue
	maxo = max(d.values())
	for j in s.prime:
		if j in d and d[j] == maxo:
			print(j)
			break


import math

def primeFactors(n):
	dicti = {}
	while n % 2 == 0:
		dicti[2] = dicti.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			dicti[i] = dicti.get(i, 0) + 1
			n = n // i
	if n > 2:
		dicti[n] = dicti.get(n, 0) + 1
	temp = max(dicti.values())
	for i in dicti:
		if dicti[i] == temp:
			print(i)
			return
for i in range(int(input())):
	n = int(input())
	primeFactors(n)


import math
from collections import Counter

def pf(n, x):
	while n % 2 == 0:
		x.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			x.append(i)
			n = n / i
	if n > 2:
		x.append(n)
for _ in range(int(input())):
	n = int(input())
	x = []
	pf(n, x)
	a = Counter(x).most_common(1)[0][0]
	print(a)


for _ in range(int(input())):
	n = int(input())
	answ = n
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			l.append(i)
			n = n / i
		i += 1
	if n > 2:
		l.append(n)
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ans = 1
	for i in d:
		ans = max(ans, d[i])
	for i in d:
		if d[i] == ans:
			answ = min(answ, i)
	print(answ)


from collections import defaultdict

def primes(n):
	primfac = defaultdict(lambda : 0)
	d = 2
	while d * d <= n:
		while n % d == 0:
			primfac[d] += 1
			n //= d
		d += 1
	if n > 1:
		primfac[n] += 1
	return primfac
T = int(input())
for _ in range(T):
	N = int(input())
	dic = primes(N)
	lis = [(k, dic[k]) for k in dic.keys()]
	print(max(lis, key=lambda tupl: (tupl[1], -tupl[0]))[0])


import math
test_cases = int(input())

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 most_frequent(List):
	counter = 0
	num = List[0]
	for i in List:
		curr_frequency = List.count(i)
		if curr_frequency > counter:
			counter = curr_frequency
			num = i
	return num
while test_cases != 0:
	n = int(input())
	l = primeFactors(n)
	k = most_frequent(l)
	print(k)
	test_cases -= 1


import math

def mergeSort(lst, start, end):
	if start == end:
		return 0
	middle = start + (end - start) // 2
	a = mergeSort(lst, start, middle)
	b = mergeSort(lst, middle + 1, end)
	c = merge(lst, start, middle, end)
	return a + b + c

def merge(lst, start, middle, end):
	count = 0
	Llst = lst[start:middle + 1]
	Rlst = lst[middle + 1:end + 1]
	n1 = len(Llst)
	i = 0
	j = 0
	k = start
	while i < middle - start + 1 and j < end - middle:
		if Llst[i] <= Rlst[j]:
			lst[k] = Llst[i]
			i += 1
			k += 1
		else:
			count += n1 - i
			lst[k] = Rlst[j]
			j += 1
			k += 1
	while i < middle - start + 1:
		lst[k] = Llst[i]
		i += 1
		k += 1
	while j < end - middle:
		lst[k] = Rlst[j]
		j += 1
		k += 1
	return count
t = int(input())
for k in range(t):
	n = int(input())
	dic = {}
	while n % 2 == 0:
		dic[2] = dic.get(2, 0) + 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			dic[i] = dic.get(i, 0) + 1
			n = n / i
	if n > 2:
		dic[n] = dic.get(n, 0) + 1
	maxi = 0
	ans = 0
	for (key, value) in dic.items():
		if value >= maxi:
			if maxi == value:
				ans = min(ans, key)
			else:
				ans = key
			maxi = value
	print(ans)


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

def primeFactors(n):
	m = {}
	while n % 2 == 0:
		if 2 in m:
			m[2] += 1
		else:
			m[2] = 1
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
			n = n // i
	if n > 2:
		m[n] = 1
	return m
for _ in range(int(input())):
	n = int(input())
	f = primeFactors(n)
	tot = 1
	for v in f:
		tot *= f[v] + 1
	k = 1
	fact = 1
	for v in f:
		cur_fact = tot // (f[v] + 1) * f[v]
		if cur_fact > fact:
			fact = cur_fact
			k = v
	if k == 1:
		k = n
	print(k)


max_prime = int(10 ** 4.5)

def GetPrimes(max_prime):
	is_prime = [True for _ in range(max_prime + 1)]
	primes = []
	for n in range(2, max_prime + 1):
		if is_prime[n]:
			primes += [n]
			for m in range(2 * n, max_prime + 1, n):
				is_prime[m] = False
	return primes
primes = GetPrimes(max_prime)

def GetPrimeFactors(n):
	powers = {}
	for prime in primes:
		while n % prime == 0:
			if prime in powers:
				powers[prime] += 1
			else:
				powers[prime] = 1
			n //= prime
	if n > 1:
		powers[n] = 1
	return powers
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	powers = GetPrimeFactors(n)
	prime_factors = sorted(powers)
	prod = 1
	for prime_factor in powers:
		prod *= 1 + powers[prime_factor]
	best_k = None
	max_num_divisors_of_m = 0
	for k in prime_factors:
		num_divisors_of_m = max(powers[k], 1) * prod // (powers[k] + 1)
		if num_divisors_of_m > max_num_divisors_of_m:
			max_num_divisors_of_m = num_divisors_of_m
			best_k = k
	print(best_k)


def prime_factors(n):
	fact = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n //= i
				cnt += 1
			fact.append([i, cnt])
		else:
			i += 1
	if n > 1:
		fact.append([n, 1])
	return fact
t = int(input())
for i in range(t):
	n = int(input())
	fact = prime_factors(n)
	fact.sort(key=lambda x: [-x[1], x[0]])
	print(fact[0][0])


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)
t = int(input())
for _ in range(t):
	n = int(input())
	d = prime_factors(n)
	print(-1 * sorted([(d[i], -1 * i) for i in d], reverse=True)[0][1])


from math import sqrt

def factor(n, dic):
	p = int(sqrt(n))
	while n % 2 == 0:
		if 2 in dic.keys():
			dic[2] += 1
		else:
			dic[2] = 1
		n = n // 2
	for i in range(3, p + 1, 2):
		while n % i == 0:
			if i in dic.keys():
				dic[i] += 1
			else:
				dic[i] = 1
			n = n // i
	if n > 2:
		dic[n] = 1
	return dic
T = int(input())
for tc in range(T):
	n = int(input())
	dic = factor(n, {})
	x = 1
	for key in dic.keys():
		x = x * (dic[key] + 1)
	res = 0
	y = 0
	for keys in dic.keys():
		if x // (dic[keys] + 1) * dic[keys] > y:
			res = keys
			y = x // (dic[keys] + 1) * dic[keys]
	print(res)


import sys
from math import sqrt, gcd
from collections import deque
sys.setrecursionlimit(10 ** 8)
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 factor(n):
	while n % 2 == 0:
		if 2 in d:
			d[2] += 1
		else:
			d[2] = 1
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			n //= i
	if n > 2:
		d[n] = 1
for _ in range(I()):
	n = I()
	d = {}
	factor(n)
	t = 1
	for i in d:
		t *= d[i] + 1
	ans = 0
	m = 0
	for i in d:
		if t // (d[i] + 1) * d[i] > m:
			ans = i
			m = t // (d[i] + 1) * d[i]
	print(ans)


import random
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007

def BF(n):
	poss = set()
	for i in range(2, n + 1):
		if n % i == 0:
			poss.add((n // i, i))
	poss = sorted(list(poss), key=lambda x: x[1])
	numdivs = -float('inf')
	res = -1
	for i in poss:
		divs = 0
		for j in range(1, i[0] + 1):
			if i[0] % j == 0:
				divs += 1
		if divs > numdivs:
			numdivs = divs
			res = i[1]
	return res

def pf(n):
	pf = Counter()
	while n % 2 == 0:
		pf[2] += 1
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			pf[i] += 1
			n //= i
	if n > 1:
		pf[n] += 1
	return pf
for i in range(stdint()):
	n = stdint()
	pfs = pf(n)
	total = 1
	for i in pfs:
		total *= pfs[i] + 1
	curr = -float('inf')
	res = float('inf')
	for i in pfs:
		pos = total // (pfs[i] + 1)
		pos *= pfs[i]
		if pos > curr:
			curr = pos
			res = i
		elif pos == curr:
			res = min(res, i)
	print(res)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 200001
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def expo(a, b):
	if not b:
		return 1
	v = expo(a, b // 2)
	v = v * v % mod
	if b % 2:
		v = v * a % mod
	return v

def modinv(a, b):
	d = expo(b, mod - 2)
	v = a * d % mod
	return v

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

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1

def isVowel(char):
	return char.lower() in 'aeiou'

def primeFactors(n):
	m = n
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		n = n // 2
		d[2] += 1
	i = 3
	while n > 1 and i * i <= m:
		while n % i == 0:
			n = n // i
			d[i] += 1
		i += 2
	if n > 1:
		d[n] += 1
	return list(d.items())
for _ in range(int(input())):
	n = int(input())
	pf = primeFactors(n)
	m = len(pf)
	l = [1 for _ in range(m + 1)]
	r = [1 for _ in range(m + 1)]
	for i in range(m):
		l[i + 1] = l[i] * (pf[i][1] + 1)
	for i in range(m - 1, -1, -1):
		r[i] = r[i + 1] * (pf[i][1] + 1)
	ans = inf
	res = 0
	for i in range(m):
		cur = l[i] * r[i + 1] * pf[i][1]
		if cur > res:
			res = cur
			ans = pf[i][0]
		elif cur == res:
			ans = min(ans, pf[i][0])
		else:
			pass
	print(ans)


import math

def fun(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n / i
	if n > 2:
		ans.append(int(n))
	obj = {}
	for x in ans:
		obj[x] = 0
	for x in ans:
		obj[x] += 1
	fac = list(obj.keys())
	fac.sort(key=lambda x: (obj[x], -1 * x), reverse=True)
	return fac[0]
t = int(input())
for TTT in range(t):
	n = int(input())
	ans = fun(n)
	print(ans)


import math

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n / i
	if n > 2:
		ans.append(int(n))
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	c = primeFactors(n)
	now = {}
	for i in c:
		if i in now:
			now[i] += 1
		else:
			now[i] = 1
	mi = float('inf')
	zero = 0
	for i in now:
		now[i] -= 1
		c = 1
		for j in now:
			if now[j] >= 1:
				c *= now[j] + 1
		if c > zero:
			mi = i
			zero = c
		elif c == zero:
			mi = min(mi, i)
		now[i] += 1
	print(mi)


import math
from collections import Counter

def factor(n):
	result = []
	while n % 2 == 0 and n > 0:
		result.append(2)
		n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			n = n // i
			result.append(i)
		else:
			i += 2
	if n > 1:
		result.append(n)
	return result
for _ in range(int(input())):
	n = int(input())
	data = factor(n)
	cnt = Counter(data)
	most = -1
	result = -1
	for (key, value) in sorted(cnt.items()):
		if value > most:
			result = key
			most = value
	print(result)


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
sys.setrecursionlimit(10 ** 8)
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353
mx = 10 ** 5 + 2
a = [1 for i in range(mx)]
a[0] = 0
a[1] = 0
p = 2
while p * p < mx:
	if a[p] == 1:
		for j in range(p * p, mx, p):
			a[j] = 0
	p += 1
pr = []
for i in range(mx):
	if a[i]:
		pr.append(i)
for _ in range(ii()):
	n = ii()
	ans = 2
	d = {}
	for i in pr:
		if n % i == 0:
			while n % i == 0:
				d[i] = d.get(i, 0) + 1
				n //= i
	if n > 1:
		d[n] = 1
	mn = 0
	for i in d:
		if mn < d[i]:
			mn = d[i]
			ans = i
	print(ans)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
prime = []
sz = 32000
stat = [0] * sz
stat[0] = 1
stat[1] = 1
for i in range(2, int(sqrt(sz)) + 1):
	if stat[i] == 0:
		for j in range(i * i, sz, i):
			stat[j] = 1
for i in range(sz):
	if stat[i] == 0:
		prime.append(i)
for _ in range(int(input())):
	n = int(input())
	l = []
	for p in range(2, 3):
		if n == 1:
			break
		c = 0
		while n % p == 0:
			n //= p
			c += 1
		l.append((c, -p))
	for p in prime:
		if n == 1:
			break
		c = 0
		while n % p == 0:
			n //= p
			c += 1
		l.append((c, -p))
	if n != 1:
		l.append((1, -n))
	l.sort()
	print(-l[-1][-1])


from sys import stdin
input = stdin.readline
size = 10 ** 5 + 1
isprime = [True] * size
isprime[0] = False
isprime[1] = False
prime = []
for i in range(2, size):
	if isprime[i]:
		for j in range(i + i, size, i):
			isprime[j] = False
		prime.append(i)

def answer():
	mval = 0
	(ans, i) = (n, 0)
	while prime[i] * prime[i] <= n:
		(x, count) = (n, 0)
		while x % prime[i] == 0:
			x //= prime[i]
			count += 1
		if mval < count:
			ans = prime[i]
			mval = count
		i += 1
	return ans
for T in range(int(input())):
	n = int(input())
	print(answer())


for i in range(int(input())):
	n = int(input())
	primes = {}
	i = 2
	while i * i <= n:
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n //= i
				cnt += 1
			primes.update({i: cnt})
		i += 1
	else:
		if n > 1:
			primes.update({n: 1})
	maxi = -1
	ind = 0
	for j in primes.keys():
		if primes[j] > maxi:
			maxi = primes[j]
			ind = j
	print(ind)