Witua is a little student from the University of Lviv. He enjoys studying math. Witua knows a lot of famous mathematicians like Eratosthenes, Pythagoras, Fermat, Diophantus, Furko, Gauss and so on. However, his favorite one is Euler. The only thing Witua likes more than Euler is Euler’s totient function φ. He is exploring the nature of this function. One of the steps of his work is finding φ(i)/i for all 2≤i≤N. He doesn’t need to know every such value, but Witua wonders for what value i, is φ(i)/i the maximum he can get? Help little student to find such i that φ(i)/i is maximum among all the  2≤i≤N.

-----Input-----
The first line contains single integer T - the number of test cases. Each of the next T lines contains a single integer N. 

-----Output-----
For every test case output i such that φ(i)/i is maximum among all i (2≤i≤N) in a separate line.

-----Constrains-----
T (1≤T≤500 )

N(2≤N≤10^18)


-----Example-----
Input:
3
2
3
4

Output:
2
3
3

Explanationφ(2)/2=1/2
φ(3)/3=2/3
φ(4)/4=2/4

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def bigmod(x, n, mod):
	ans = 1
	while n > 0:
		if n % 2 == 1:
			ans = ans * x % mod
		n >>= 1
		x = x * x % mod
	return ans

def check_composite(n, a, d, s):
	x = bigmod(a, d, n)
	if x == 1 or x == n - 1:
		return False
	for r in range(s - 1):
		x = x * x % n
		if x == 1:
			return True
		if x == n - 1:
			return False
	return True

def MillerRabin(n, iter=1):
	if n < 2:
		return False
	r = 0
	d = n - 1
	while d % 2 == 0:
		d >>= 1
		r += 1
	primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	for a in primes:
		if n == a:
			return True
		elif n % a == 0:
			return False
		if check_composite(n, a, d, r) == True:
			return False
	return True
t = int(input())
for cas in range(t):
	n = int(input())
	if n == 2:
		print(2)
		continue
	if n % 2 == 0:
		n -= 1
	while MillerRabin(n) == False:
		n -= 2
	print(n)


def is_strong_psp(b, n):
	n1 = n - 1
	e = (n1 ^ n1 - 1).bit_length() - 1
	d = n1 >> e
	b = pow(b, d, n)
	if b in [1, n - 1]:
		return True
	for i in range(e - 1):
		b = pow(b, 2, n)
		if b == n - 1:
			return True
	return False
bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]

def is_prime(n):
	if n <= 28:
		return n in bases
	for x in bases:
		if n % x == 0:
			return False
	for x in bases:
		if not is_strong_psp(x, n):
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(2)
		continue
	if n % 2 == 0:
		n -= 1
	assert n >= 3
	while True:
		if is_prime(n):
			print(n)
			break
		n -= 2


import math
import random

def miller_rabin_pass(a, n):
	d = n - 1
	s = 0
	while d % 2 == 0:
		d >>= 1
		s += 1
	a_to_power = pow(a, d, n)
	if a_to_power == 1:
		return True
	for i in range(s - 1):
		if a_to_power == n - 1:
			return True
		a_to_power = a_to_power * a_to_power % n
	return a_to_power == n - 1

def isprime(n):
	for repeat in range(20):
		a = 0
		while a == 0:
			a = random.randrange(n)
		if not miller_rabin_pass(a, n):
			return False
	return True
t = int(input())
for i in range(t):
	x = int(input())
	if x == 2:
		print('2')
		continue
	if x % 2 == 0:
		x = x - 1
	while x > 1:
		if isprime(x):
			print(x)
			break
		x = x - 2


def modular_pow(base, exponent, modulus):
	result = 1
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		exponent = exponent // 2
		base = base * base % modulus
	return result

def passesMillerRabinTest(n, a):
	s = 0
	d = n - 1
	while d % 2 == 0:
		s += 1
		d >>= 1
	x = modular_pow(a, d, n)
	if x == 1 or x == n - 1:
		return True
	for ss in range(s - 1):
		x = x * x % n
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False
primeList = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

def isPrime(n):
	for p in primeList:
		if n % p == 0:
			return n == p
	for p in primeList:
		if passesMillerRabinTest(n, p) == False:
			return False
	return True
t = int(input())
for tt in range(t):
	n = int(input())
	if n == 2:
		print(2)
		continue
	if n % 2 == 0:
		n -= 1
	while True:
		if isPrime(n):
			print(n)
			break
		n -= 2


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]

def millerTest(d, n, p):
	x = pow(p, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isPrime(n):
	if n in primes:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for p in primes:
		if not millerTest(d, n, p):
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	while not isPrime(n):
		n -= 1
	print(n)


from math import sqrt

def miller_rabin_pass(s, d, n):
	atp = pow(2, d, n)
	if atp == 1 or atp == n - 1:
		return True
	for i in range(s - 1):
		atp = atp * atp % n
		if atp == n - 1 or atp == 1:
			return True
	return False

def miller_rabin(n):
	if n == 1373653 or n == 25326001 or n == 3215031751 or (n == 2152302898747) or (n == 3474749660383) or (n == 341550071728321):
		return False
	v = sqrt(n)
	for x in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
		if x > v:
			return True
		if n % x == 0:
			return False
	d = n - 1
	s = 0
	while not d & 1:
		d >>= 1
		s += 1
	if not miller_rabin_pass(s, d, n):
		return False
	return True

def f(n):
	skip = [1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6]
	if n == 2:
		return n
	if n % 2 == 0:
		n -= 1
	mod = n % 30
	while not miller_rabin(n):
		n -= skip[mod]
		mod -= skip[mod]
		if mod < 0:
			mod += 30
	return n
c = int(input())
for i in range(c):
	print(f(int(input())))


import random
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23]
K = 5

def power(a, p, mod):
	if p == 0 or a == 1:
		return 1
	if p == 1:
		return a % mod
	m = power(a, p // 2, mod)
	return m * m * power(a, p % 2, mod) % mod

def get_sd(n):
	s = 0
	while n % 2 == 0:
		s += 1
		n = n // 2
	return (s, n)

def check_for_a(a, s, d, n):
	x = power(a, d, n)
	if x == 1 or x == n - 1:
		return True
	for i in range(s - 1):
		x = x * x % n
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isprime(n):
	(s, d) = get_sd(n - 1)
	for a in PRIMES:
		if a > n:
			break
		if n % a == 0:
			return n == a
		if not check_for_a(a, s, d, n):
			return False
	return True

def biggest_prime(n):
	if n == 2:
		return n
	if n % 2 == 0:
		n -= 1
	while True:
		if isprime(n):
			return n
		n -= 2
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	print(biggest_prime(n))


CNT = 20
A = 3312412834612873462378467
B = 5514141562731294354999181
MOD = 2 ** 64 - 1
CUR = 132412342151345666641

def nextRandomValue():
	global CUR
	CUR = CUR * A + B
	CUR %= MOD
	return CUR

def Pow(val, p, mod):
	res = 1
	while p > 0:
		if p % 2 == 1:
			res = res * val % mod
		val = val * val % mod
		p //= 2
	return res % mod

def isPrime(val):
	if val == 2 or val == 3:
		return True
	if val < 2 or val % 2 == 0:
		return False
	s = 0
	t = val - 1
	while t % 2 == 0:
		t //= 2
		s += 1
	for i in range(0, CNT):
		r = 2 + nextRandomValue() % (val - 3)
		x = Pow(r, t, val)
		if x == 1 or x == val - 1:
			continue
		flag = False
		for j in range(0, s - 1):
			x = x * x % val
			if x == val - 1:
				flag = True
		if not flag:
			return False
	return True
t = int(input())
for T in range(0, t):
	n = int(input())
	ans = n
	while not isPrime(ans):
		ans -= 1
	print(str(ans))


import sys, random
LOW_BORDER = 10
TRY = 50

def readInt():
	return int(input())

def readList():
	return list(map(int, input().strip().split(' ')))

def readStr():
	return input().strip()

def makeMatrix(a, b, value):
	z = [value] * a
	for i in range(a):
		z[i] = [value] * b
	return z

def gcd(a, b):
	while a:
		(a, b) = (b % a, a)
	return b

def yakobi(a, p):
	if a == 1:
		return 1
	if a == 2:
		if (p * p - 1) // 8 % 2 == 0:
			return 1
		return -1
	if a % 2 == 0:
		res = 1
		while a % 2 == 0:
			a //= 2
			res *= yakobi(2, p)
		return res * yakobi(a, p)
	if (a - 1) // 2 * ((p - 1) // 2) % 2 == 0:
		return yakobi(p % a, a)
	else:
		return -yakobi(p % a, a)

def bruteForce(p):
	if p == 2:
		return True
	if p % 2 == 0:
		return False
	t = 3
	while t * t <= p:
		if p % t == 0:
			return False
		t += 2
	return True

def power(a, k, m):
	r = 1
	while k:
		if k & 1:
			r = r * a % m
		k //= 2
		a = a * a % m
	return r

def solovey_shtrassen(p):
	if p <= LOW_BORDER:
		return bruteForce(p)
	m = (p - 1) // 2
	for i in range(TRY):
		a = random.randint(2, p - 1)
		if gcd(a, p) != 1:
			return False
		pp = power(a, m, p)
		if pp != 1:
			pp = -1
		if pp != yakobi(a, p):
			return False
	return True

def phi(x):
	res = 0
	for i in range(1, x + 1):
		if gcd(i, x) == 1:
			res += 1
	return res
tc = readInt()
while tc:
	tc -= 1
	n = readInt()
	while solovey_shtrassen(n) == False:
		n -= 1
	print(n)


t = int(input())
for i in range(t):
	n = int(input())
	l = [2, 3, 5, 7, 11, 13, 17, 19, 23]

	def snek1(d, n, p):
		x = pow(p, d, n)
		if x == 1 or x == n - 1:
			return True
		while d != n - 1:
			x = x * x % n
			d *= 2
			if x == 1:
				return False
			if x == n - 1:
				return True
		return False

	def prime(n):
		if n in l:
			return True
		d = n - 1
		while d % 2 == 0:
			d //= 2
		for p in l:
			if not snek1(d, n, p):
				return False
		return True
	if n == 2:
		print('2')
	elif n == 3:
		print('3')
	else:
		for j in range(n):
			if prime(n - j) == True:
				print(n - j)
				break


import math

def isprime(n):
	primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	if n in primes:
		return 1
	elif n % 2:
		for prime in primes:
			temp = n - 1
			times = 0
			while temp % 2 == 0:
				temp = temp // 2
				times = times + 1
			value = pow(prime, temp, n)
			if value == 1 or value == n - 1:
				continue
			if times:
				flag = 0
				for i in range(times - 1):
					value = value * value % n
					if value == n - 1:
						flag = 1
						break
				if flag:
					continue
			return 0
		return 1
	else:
		return 0
T = int(input())
for i in range(T):
	N = int(input())
	temp = N
	while temp >= 2:
		if isprime(temp):
			break
		temp = temp - 1
	print(temp)


def mul(a, b, mod):
	res = 0
	while b:
		if b & 1:
			res = (res + a) % mod
		a = 2 * a % mod
		b >>= 1
	return res

def checkCom(n, a, d, s):
	x = pow(a, d, n)
	if x == 1 or x == n - 1:
		return False
	for r in range(s):
		x = mul(x, x, n)
		if x == n - 1:
			return False
	return True

def isPrime(n):
	if n < 4:
		return n == 2 or n == 3
	s = 0
	d = n - 1
	while d & 1 == 0:
		d >>= 1
		s += 1
	for prime in [2, 3, 5, 7, 11, 13, 17, 19, 23]:
		if n == prime:
			return True
		if checkCom(n, prime, d, s):
			return False
	return True

def fun():
	n = int(input())
	if n > 2:
		if n % 2 == 0:
			n -= 1
		while True:
			if isPrime(n):
				break
			n -= 2
	print(n)
t = int(input())
while t:
	t -= 1
	fun()


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]

def millerTest(d, n, p):
	x = pow(p, d, n)
	if x == 1 or x == n - 1:
		return True
	while d != n - 1:
		x = x * x % n
		d *= 2
		if x == 1:
			return False
		if x == n - 1:
			return True
	return False

def isProbablePrime(n):
	if n in primes:
		return True
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for p in primes:
		if not millerTest(d, n, p):
			return False
	return True
t = int(input())
for test in range(t):
	N = int(input())
	if N == 1:
		print(1)
	for i in range(N, 0, -1):
		if isProbablePrime(i):
			print(i)
			break