You are given an integer N. Find another integer X (X > N) such that the following conditions are satisfied :

1. X is not a multiple of N.
2. The value  |gcd(N,X)-lcm(N,X)| is as small as possible.

If there are multiple answers for X, print any.

For reference, gcd(u, v) is the [greatest common divisor] between u and v, while lcm(u, v) refers to the [least common multiple].

------ 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.
- The first line of each test case contains an integer N.

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

For each testcase, print any suitable X satisfying the above two conditions for the given N.

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

$1 ≤T ≤1000$
$2 ≤N ≤10^{12}$.
- Sum of $N$ over all testcases won't exceed $5*10^{12}$.

------ subtasks ------ 

Subtask 1 (10 points): $2 ≤ N ≤ 1000$
Subtask 2 (20 points): $2 ≤ N ≤ 10^{6}$
Subtask 3 (70 points): $2 ≤ N ≤ 10^{12}$

----- Sample Input 1 ------ 
2
3
4
----- Sample Output 1 ------ 
4
6
----- explanation 1 ------ 
1.In first case , $GCD(3,4)$ =$1$ and $LCM(3,4)$= $12$ , $|1-12|$= $11$. $11$ is the smallest value we can get by choosing $X$ as 4.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
from math import sqrt

def prime(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 False

def printDivisors(n):
	i = 2
	d = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				return i
			else:
				return min(i, n // i)
		i = i + 1
	return d
for i in range(int(input())):
	m = int(input())
	if prime(m):
		print(m + 1)
	else:
		w = printDivisors(m)
		print((w + 1) * (m // w))


import math
from math import sqrt

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

def snek2(n):
	c = 2
	d = []
	while c <= math.sqrt(n):
		if n % c == 0:
			if n / c == c:
				return c
			else:
				return min(c, n // c)
		c += 1
	return d
t = int(input())
for i in range(t):
	m = int(input())
	if snek(m):
		print(m + 1)
	else:
		w = snek2(m)
		print((w + 1) * (m // w))


import math, sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
compute_lcm = lambda x, y: x * y // math.gcd(x, y)
for t_itr in range(int(input())):
	n = int(input())
	p = 1
	current_min = 10 ** 20
	out = (n, n + 1)
	while p * p <= n:
		if n % p == 0:
			flag1 = abs(compute_lcm(n, n + p) - math.gcd(n, n + p))
			flag2 = flag1 + 1
			if n + n // p != 2 * n:
				flag2 = abs(compute_lcm(n, n + n // p) - math.gcd(n, n + n // p))
			cpl = (n, n + p)
			if flag2 <= flag1:
				cpl = (n, n + n // p)
			flag = min(flag1, flag2)
			if flag <= current_min:
				out = cpl
				current_min = min(current_min, flag)
		p += 1
	print(out[1])


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(n * 3 // 2)
	else:
		i = 2
		flag = 0
		while i * i <= n:
			if n % i == 0:
				print(n * (i + 1) // i)
				flag = 1
				break
			i += 1
		if flag == 0:
			print(n + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = 1
	b = n
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			a = i
			b = n // i
			break
	if a == 1:
		print(a * (b + 1))
	else:
		print(b * (a + 1))


import sys
input = sys.stdin.readline

def GetPrimes(max_prime=10 ** 6):
	primes = []
	is_prime = [True for n in range(max_prime + 1)]
	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

def GetSmallestPrimeFactor(x):
	if x in primes_set:
		return x
	for prime in primes:
		if x % prime == 0:
			return prime
	return x
primes = GetPrimes()
primes_set = set(primes)
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	smallest_prime_factor = GetSmallestPrimeFactor(n)
	biggest_factor = n // smallest_prime_factor
	print(n + biggest_factor)


from math import sqrt

def get_lowest_prime_multiple(N):
	if N % 2 == 0:
		return 2
	for j in range(3, int(sqrt(N)) + 1, 2):
		if N % j == 0:
			return j
	return N
T = int(input())
for i in range(T):
	N = int(input())
	l_prime = get_lowest_prime_multiple(N)
	ans = N // l_prime * (l_prime + 1)
	print(ans)


from math import ceil, sqrt
for _ in range(int(input())):
	n = int(input())
	n1 = n
	d = dict()
	flag = 0
	s = 0
	for i in range(2, ceil(sqrt(n)) + 1):
		if n % i == 0:
			n //= i
			d[i] = d[i] + 1 if d.get(i) else 1
			if not flag:
				flag = 1
				s = i
				break
	d[n] = d[n] + 1 if d.get(n) else 1
	if not flag:
		print(n1 + 1)
	else:
		print(n1 // 2 * 3) if s == 2 else print(n1 // s * (s + 1))


from math import *
t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	n1 = n
	d = dict()
	i = 2
	flag = 0
	s = 0
	while ceil(sqrt(n)) >= i:
		if n % i == 0:
			n = n // i
			if d.get(i):
				d[i] = d[i] + 1
			else:
				d[i] = 1
			if flag == 0:
				flag = 1
				s = i
				break
		else:
			i = i + 1
	d[n] = d[n] + 1 if d.get(n) else 1
	if not flag:
		print(n1 + 1)
	else:
		print(n1 // 2 * 3) if s == 2 else print(n1 // s * (s + 1))


for _ in range(int(input())):
	n = int(input())
	d = 10 ** 18
	ans1 = 0
	s = int(n ** (1 / 2))
	s += 1
	for i in range(1, s):
		if n % i == 0:
			t = n // i
			j = t
			t += 1
			x = t * i
			if x % n == 0:
				continue
			ans = x * n // i
			ans = abs(i - ans)
			if ans < d:
				ans1 = x
				d = ans
			t = n // j
			t += 1
			x = t * j
			if x % n == 0:
				continue
			ans = x * n // j
			ans = abs(j - ans)
			if ans < d:
				ans1 = x
				d = ans
	print(ans1)


from sys import stdin
input = stdin.readline

def prime_factors(x):
	prime_factors = []
	i = 2
	while x > 1:
		if i ** 2 > x:
			i = x
		while x % i == 0:
			prime_factors.append(i)
			x //= i
		i += 1 + (i > 2)
	return prime_factors
t = int(input())
for _ in range(t):
	n = int(input())
	m = min(prime_factors(n))
	ans = n // m * (m + 1)
	print(ans)


import math
from random import randint

def timeTaken(func):
	from time import time

	def decorator(*args, **kwargs):
		start = time()
		returned = func(*args, **kwargs)
		end = time()
		if int(100 * (end - start)) / 100 > 0.01:
			print('Time taken is: ', int(100 * (end - start)) / 100, 'Sec')
		return returned
	return decorator

def memoize(func):
	mem = {}

	def memoizer(*args, **kwargs):
		key = str(args) + str(kwargs)
		if key not in mem:
			mem[key] = func(*args, **kwargs)
		return mem[key]
	return memoizer

def counter(lst):
	q = [0] * max(lst)
	for i in range(len(lst)):
		q[lst[i] - 1] = q[lst[i] - 1] + 1
	return q

def counter_elements(lst):
	q = dict()
	for x in lst:
		if x not in q:
			q[x] = 1
		else:
			q[x] += 1
	return q

def string_counter(lst):
	q = [0] * 26
	for i in range(len(lst)):
		q[ord(lst[i]) - 97] = q[ord(lst[i]) - 97] + 1
	return q

def factorial(n, m=1000000007):
	q = 1
	for i in range(n):
		q = q * (i + 1) % m
	return q

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.extend([i, n // i])
	return q

def prime_factors(n):
	q = []
	while n % 2 == 0:
		q.append(2)
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			q.append(i)
			n = n // i
	if n > 2:
		q.append(n)
	return q

def power_two(x):
	return x and (not x & x - 1)

def ceil(a, b):
	return -(-a // b)
	import bisect

def getPrimes(MAX=10 ** 5):
	primes = [2]
	for n in range(3, MAX, 2):
		sqrt_n = math.sqrt(n)
		for prime in primes:
			if prime > sqrt_n:
				primes.append(n)
				break
			if n % prime == 0:
				break
	return primes

def sieve(MAX=10 ** 5 + 1):
	spf = [i for i in range(MAX)]
	for i in range(4, MAX, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAX))):
		if spf[i] == i:
			for j in range(i * i, MAX, i):
				if spf[j] == j:
					spf[j] = i
	return spf
MOD = 10 ** 9 + 7

def mod_mul(a, b):
	return a % MOD * (b % MOD) % MOD

def mod_sum(a, b):
	return (a + b) % MOD

def mod_inv(a):
	return pow(a, MOD - 2, MOD)
import io, os, sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

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

def invr():
	return map(int, input().split())

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def Q1(S, A, B, C):
	p = S * (1 + C / 100)
	return 'YES' if p >= A and p <= B else 'NO'

def Q2(N, K):

	def hcf(x, y):
		return hcf(y, x % y) if y else x
	return N // hcf(N, K)
MOD = 998244353
Q_inv = mod_inv(4)

def Q3(N):
	return N * pow(N + 1, 2, MOD) * Q_inv % MOD

def Q4(N, B):
	B.sort()
	count = dict()
	for b in B:
		if b not in count:
			count[b] = 1
		else:
			count[b] += 1
	even = sum((1 for x in count if not count[x] % 2))
	if N == 1:
		return [B[0]] if B[0] == B[1] else [-1]
	else:
		m = N - 1 if N % 2 else N - 2
		if (B[m] != B[m + 1] or B[m] != B[m + 2] or count[B[m]] != 3) or B[-1] == B[-2] or even != N - 2:
			return [-1]
		else:
			return [B[2 * i + 1] for i in range(N - 1)] + [B[-1]]

def Q5(N):
	mn = min(prime_factors(N))
	return N * (mn + 1) // mn
for _ in range(inp()):
	outp(Q5(inp()))


import math
t = int(input())
for tc in range(0, t):
	n = int(input())
	flag = False
	x = math.floor(math.sqrt(n))
	ans = 0
	quo = 0
	if n > 1:
		for i in range(2, x + 1):
			if n % i == 0:
				quo = n / i
				ans = n + quo
				flag = True
				break
		if flag:
			print(int(ans))
		else:
			print(n + 1)


def low_mul(n):
	s = int(n ** 0.5)
	for i in range(2, s + 1):
		if n % i == 0:
			return i
	return n
t = int(input())
for k in range(t):
	n = int(input())
	a = low_mul(n)
	b = n // a
	x = (a + 1) * b
	print(x)


from math import ceil, gcd, inf, sqrt
for _ in range(int(input())):
	n = int(input())
	factors = []
	for i in range(1, ceil(sqrt(n)) + 1):
		if n % i != 0:
			continue
		(a, b) = (i, n // i)
		factors.append(a)
		factors.append(b)
		factors = list(set(factors))
		factors.sort()
	print(n + factors[-2])


try:
	for _ in range(int(input())):
		n = int(input())
		j = 2
		ok = 0
		while j * j <= n:
			if n % j == 0:
				ok = 1
				break
			j += 1
		b = j
		if ok == 0:
			b = 1
		if b != 1:
			b = max(j, n // j)
		gc = b
		print(n + b)
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	ans = n + 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			ans = n + n // i
			break
	print(ans)


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
t = int(input())
for _ in range(t):
	n = int(input())
	k = smallestDivisor(n)
	a = n // k
	print(a * (k + 1))


from math import sqrt

def checkprime(i):
	prime_flag = 0
	for j in range(2, int(sqrt(i)) + 1):
		if i % j == 0:
			prime_flag = 1
			break
	if prime_flag == 0:
		return True
	else:
		return False
for i in range(int(input())):
	n = int(input())
	if checkprime(n) == True:
		print(n + 1)
		continue
	for j in range(2, n + 1):
		if checkprime(j) == True:
			if n % j == 0:
				print(int(n // j) * (j + 1))
				break


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(3 * n // 2)
	else:
		fc = 0
		for i in range(3, math.floor(math.sqrt(n)) + 1, 2):
			if n % i == 0:
				fc = n // i
				count = i
				break
		if fc != 0:
			print(fc * (count + 1))
		else:
			print(n + 1)


t = int(input())
for i in range(t):
	n = int(input())
	num = 1
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			num = i
			break
	if num == 1:
		print(n + 1)
	else:
		print(n // num + n)


import math
for i in range(int(input())):
	n = int(input())
	if n & 1:
		f = 0
		for i in range(3, int(math.sqrt(n)) + 1):
			if n % i == 0:
				f = n // i
				break
		if f != 0:
			print(f * (i + 1))
		else:
			print(n + 1)
	else:
		print(3 * n // 2)


import math
t = int(input())
while t != 0:
	n = int(input())
	if n % 2 == 0:
		print(3 * n // 2)
	else:
		big_factor = 0
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			if n % i == 0:
				big_factor = n / i
				break
		if big_factor != 0:
			print(int(big_factor * (i + 1)))
		else:
			print(n + 1)
	t -= 1


import math

def primeFactors(n):
	mul = []
	num = 1
	mi = n
	while n % 2 == 0:
		mul.append(2)
		num *= 2
		mi = min(mi, 2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			mul.append(i)
			num *= i
			mi = min(mi, i)
			n = n // i
	if n > 2:
		num *= n
		mul.append(n)
		mi = min(mi, n)
	return (mul, num, mi)
for tc in range(int(input())):
	n = int(input())
	res = primeFactors(n)
	if len(res[0]) == 1:
		print(n + 1)
	else:
		print(res[1] // res[2] * (res[2] + 1))


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		x = n // 2 * 3
		print(x)
	else:
		ok = False
		for i in range(3, int(n ** 0.5) + 1):
			if n % i == 0:
				ok = True
				x = n // i * (i + 1)
				print(x)
				break
		if not ok:
			print(n + 1)


import math

def isp(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return n
from math import sqrt

def isPr(n):
	if n <= 1:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	x = isp(n)
	if isPr(n):
		print(n + 1)
	else:
		print((x + 1) * (n // x))


import math

def factor(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 b
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	x = factor(n)
	x[0] = x[0] + 1
	sum = 1
	for i in x:
		sum = sum * i
	print(sum)


import math
for _ in range(int(input())):
	n = int(input())
	ans = 1
	if n % 2 == 0:
		ans = 3 * n // 2
	else:
		sf = 0
		for i in range(3, math.ceil(math.sqrt(n)) + 1):
			if n % i == 0:
				sf = n // i
				break
		if sf != 0:
			ans = sf * (i + 1)
		else:
			ans = n + 1
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(n // 2 * 3)
	else:
		fl = 0
		for j in range(3, int(math.sqrt(n) + 1), 2):
			if n % j == 0:
				fl = j
				break
		if fl == 0:
			print(n + 1)
		else:
			print(n // fl * (fl + 1))


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		ans = n * 3 // 2
	else:
		temp = 0
		for i in range(3, int(n ** 0.5) + 1, 2):
			if n % i == 0:
				temp = i
				ans = n * (i + 1) // i
				break
		if temp == 0:
			ans = n + 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(3 * n // 2)
	else:
		f = 0
		for i in range(3, int(n ** 0.5) + 1, 2):
			if n % i == 0:
				f = n // i
				break
		if f != 0:
			print(f * (i + 1))
		else:
			print(n + 1)


for _ in range(int(input())):
	n = int(input())
	h = 1
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			h = i
			break
	if h == 1:
		ans = n + 1
	else:
		ans = n + n // h
	print(ans)


import math
for i in range(int(input())):
	n = int(input())
	m = []
	l = 2
	a = n
	while l <= int(math.sqrt(n)) + 1:
		if n % l == 0:
			m.append(l)
			m.append(n // l)
			break
		else:
			l += 1
	if m == []:
		m.append(1)
	m.sort()
	v = 0
	o = 1
	for k in range(len(m) - 1, -1, -1):
		if k == 0:
			if m[k] == 1:
				v = 1
				print(a + 1)
			o = o + a
		else:
			o = o * m[k]
	if v == 0:
		print(o)


def isprime(num):
	for n in range(2, int(num ** 1 / 2) + 1):
		if num % n == 0:
			return False
	return True
import math
for i in range(int(input())):
	n = int(input())
	m = []
	l = 2
	a = n
	while l <= int(math.sqrt(n)) + 1:
		if n % l == 0:
			m.append(l)
			m.append(n // l)
			break
		else:
			l += 1
	if m == []:
		m.append(1)
	m.sort()
	v = 0
	o = 1
	for k in range(len(m) - 1, -1, -1):
		if k == 0:
			if m[k] == 1:
				v = 1
				print(a + 1)
			o = o + a
		else:
			o = o * m[k]
	if v == 0:
		print(o)


try:
	import math as m
	for i in range(int(input())):
		n = int(input())
		if n % 2 == 0:
			print(3 * n // 2)
		else:
			fc = 0
			for i in range(3, int(m.sqrt(n)) + 1, 2):
				if n % i == 0:
					fc = n // i
					break
			if fc == 0:
				print(n + 1)
			else:
				print((i + 1) * fc)
except EOFError:
	pass


from sys import stdin
input = stdin.readline

def answer():
	i = 2
	while i * i <= n:
		if n % i == 0:
			return (i + 1) * (n // i)
		i += 1
	return n + 1
for T in range(int(input())):
	n = int(input())
	print(answer())


for i in range(int(input())):
	n = int(input())

	def firstprime(x):
		for i in range(3, int(x ** 0.5) + 1, 2):
			if x % i == 0:
				return [n // i, i]
		return [0]
	if n % 2 == 0:
		print(int(n * 1.5))
	else:
		k = firstprime(n)
		if k[0] == 0:
			print(n + 1)
		else:
			print((k[1] + 1) * k[0])


try:
	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(n)
		return arr
	for t in range(int(input())):
		N = int(input())
		P = primeFactors(N)
		P.sort()
		P[0] += 1
		ans = 1
		for i in P:
			ans *= i
		print(int(ans))
except:
	pass


import math
t = int(input())
while t > 0:
	n = int(input())
	ans = 1
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			ans = n // i
			break
	print(n + ans)
	t -= 1


from math import sqrt

def gcd(p, q):
	while q != 0:
		(p, q) = (q, p % q)
	return p

def is_coprime(x, y):
	return gcd(x, y) == 1
t = int(input())
while t:
	t -= 1
	n = int(input())
	cFactor = n
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			cFactor = i
			break
	nextFactor = cFactor + 1
	while not is_coprime(nextFactor, cFactor):
		nextFactor += 1
	print(int(nextFactor * n / cFactor))


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

def solve(n):
	if isprime(n):
		print(n + 1)
	else:
		ans = 0
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				ans = i
				ans = n + int(n // ans)
				break
		print(ans)
for _ in range(int(input())):
	n = int(input())
	solve(n)


import math
lcm = lambda x, y: x * y // math.gcd(x, y)
t = int(input())
for i in range(t):
	n = int(input())
	p = 1
	curmin = 10 ** 20
	o = (n, n + 1)
	while p * p <= n:
		if n % p == 0:
			f1 = abs(lcm(n, n + p) - math.gcd(n, n + p))
			f2 = f1 + 1
			if n + n // p != 2 * n:
				f2 = abs(lcm(n, n + n // p) - math.gcd(n, n + n // p))
			cpl = (n, n + p)
			if f2 <= f1:
				cpl = (n, n + n // p)
			flag = min(f1, f2)
			if flag <= curmin:
				o = cpl
				curmin = min(curmin, flag)
		p += 1
	print(o[1])


import math
try:
	for _ in range(int(input())):
		n = int(input())
		c = math.sqrt(n)
		z = 0
		i = 2
		while i <= c:
			if n % i == 0:
				z = i
				break
			else:
				i = i + 1
		if z == 0:
			print(n + 1)
		else:
			d = (z + 1) * (n // z)
			print(d)
except:
	pass


import math
compute_lcm = lambda x, y: x * y // math.gcd(x, y)
test = int(input())
for t_itr in range(test):
	num = int(input())
	p = 1
	current_min = 10 ** 20
	out = (num, num + 1)
	while p * p <= num:
		if num % p == 0:
			flag1 = abs(compute_lcm(num, num + p) - math.gcd(num, num + p))
			flag2 = flag1 + 1
			if num + num // p != 2 * num:
				flag2 = abs(compute_lcm(num, num + num // p) - math.gcd(num, num + num // p))
			cpl = (num, num + p)
			if flag2 <= flag1:
				cpl = (num, num + num // p)
			flag = min(flag1, flag2)
			if flag <= current_min:
				out = cpl
				current_min = min(current_min, flag)
		p = p + 1
	print(out[1])


import sys
input = sys.stdin.readline
from math import ceil, floor, sqrt, gcd, log, modf
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip('\r\n')

def solve():
	n = ri()
	ans = float('inf')
	x = None
	for i in range(int(sqrt(n)), 0, -1):
		if n % i:
			continue
		g = gcd(n, n + i)
		l = (n + i) * n // g
		if abs(g - l) < ans:
			x = n + i
			ans = abs(g - l)
		d = n // i
		if d == n:
			continue
		g = gcd(n + d, n)
		l = (n + d) * n // g
		if abs(g - l) < ans:
			x = n + d
			ans = abs(g - l)
	return x
for _ in range(ri()):
	print(solve())


import math
t = int(input())
for i in range(t):
	n = int(input())
	d = 1
	if n % 2 == 0:
		d = n // 2
	else:
		for i in range(3, int(math.sqrt(n)) + 1):
			if n % i == 0:
				k = n // i
				c = max(i, k)
				d = max(d, c)
	if d == 1:
		print(n + 1)
	else:
		print(n + d)


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(int(i))
			n = n / i
	if n > 2:
		lst.append(int(n))
	return lst
for _ in range(int(input())):
	n = int(input())
	ans = primeFactors(n)
	if len(ans) == 1:
		print(n + 1)
	else:
		ans[0] += 1
		res = 1
		for i in ans:
			res *= i
		print(res)


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(n + n // 2)
		continue
	f = True
	for i in range(3, int(math.sqrt(n)) + 2):
		if n % i == 0:
			print(n + n // i)
			f = False
			break
	if f:
		print(n + 1)


import math

def solve(n):
	ans = 1000000000000000000000
	g = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			p = n / i
			num = p * (n + i) - i
			if num <= ans:
				ans = num
				g = i
			if p != n:
				num = i * (n + p) - p
				if num <= ans:
					ans = num
					g = p
	return g
t = int(input())
for j in range(0, t):
	n = int(input())
	r = int(solve(n))
	print(n + r)


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
t = int(input())
while t > 0:
	n = int(input())
	x = smallestDivisor(n)
	y = n // x
	z = y * (x + 1)
	print(z)
	t = t - 1


import math

def allDivisors(n):
	divisors = list()
	for i in range(2, round(math.sqrt(n)) + 1):
		if n % i == 0:
			divisors.append(i)
			if n // i != i:
				divisors.append(n // i)
	return divisors
T = int(input())
for t in range(T):
	N = int(input())
	ans = 10000000000000000
	res = 10000000000000000
	divisors = allDivisors(N)
	for divisor in divisors:
		X = (N // divisor + 1) * divisor
		gcd = math.gcd(N, X)
		lcm = N * X / gcd
		if abs(gcd - lcm) < res:
			res = abs(gcd - lcm)
			ans = X
	if ans == 10000000000000000:
		ans = N + 1
	print(ans)


import math

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
	return True
for _ in range(int(input())):
	n = int(input())
	ans = n + n // smallestDivisor(n)
	print(ans)


import math
compute_lcm = lambda num1, num2: num1 * num2 // math.gcd(num1, num2)
t = int(input())
for iteration in range(t):
	num = int(input())
	prime = 1
	minatThisIteration = 10 ** 20
	res = (num, num + 1)
	while prime * prime <= num:
		if num % prime == 0:
			check1 = abs(compute_lcm(num, num + prime) - math.gcd(num, num + prime))
			check2 = check1 + 1
			if num + num // prime != 2 * num:
				check2 = abs(compute_lcm(num, num + num // prime) - math.gcd(num, num + num // prime))
			cpl = (num, num + prime)
			if check2 <= check1:
				cpl = (num, num + num // prime)
			check = min(check1, check2)
			if check <= minatThisIteration:
				res = cpl
				minatThisIteration = min(minatThisIteration, check)
		prime += 1
	print(res[1])


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()
for _ in range(aint()):
	n = aint()
	f = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if n // i == i:
				pass
			else:
				f.append(n // i)
			f.append(i)
	f.sort()
	g = n // f[1]
	ans = g * (f[1] + 1)
	print(ans)


import math

def dd(n):
	ans = 1
	i = 2
	while i <= math.sqrt(n):
		if n % i == 0:
			ans = max(ans, i, n // i)
		i = i + 1
	return ans
for _ in range(int(input())):
	x = int(input())
	print(x + dd(x))


import math
compute_lcm = lambda x, y: x * y // math.gcd(x, y)
v = int(input())
for v_itr in range(v):
	c = int(input())
	p = 1
	current_min = 10 ** 20
	out = (c, c + 1)
	while p * p <= c:
		if c % p == 0:
			flag1 = abs(compute_lcm(c, c + p) - math.gcd(c, c + p))
			flag2 = flag1 + 1
			if c + c // p != 2 * c:
				flag2 = abs(compute_lcm(c, c + c // p) - math.gcd(c, c + c // p))
			cpl = (c, c + p)
			if flag2 <= flag1:
				cpl = (c, c + c // p)
			flag = min(flag1, flag2)
			if flag <= current_min:
				out = cpl
				current_min = min(current_min, flag)
		p += 1
	print(out[1])


import math
for _ in range(int(input())):
	n = int(input())
	x = 0
	if n % 2 != 0:
		ind = 1
		for i in range(1, int(math.sqrt(n)) + 1):
			if n % i == 0:
				if n // i == i and i != n:
					ind = max(ind, i)
				else:
					if i != n:
						ind = max(ind, i)
					if n // i != n:
						ind = max(ind, n // i)
		index = ind
		x = n + index
	else:
		x = x + n // 2
		x += n
	print(x)


from math import sqrt
test = int(input())
while test:
	n = int(input())
	s = found = 0
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			s = n // i
			found = 1
			break
	if found:
		print(n + s)
	else:
		print(n + 1)
	test -= 1


from math import gcd

def is_prime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def get_largest_primefactor(n):
	sm = 2
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			sm = max(sm, i, n // i)
	return sm
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(3 * n // 2)
	elif is_prime(n):
		print(n + 1)
	else:
		print(n + get_largest_primefactor(n))


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n >= 1000000:
		rm = int(math.sqrt(n))
		for m in range(2, rm + 1):
			if n % m == 0:
				break
		if m == rm:
			x = n + 1
		else:
			x = n + n // m
		print(x)
	else:
		for m in range(2, n):
			if n % m == 0:
				break
		x = n + n // m
		if m == n:
			x = n + 1
		print(x)


from math import sqrt

def isPrime(n):
	if n == 0:
		return 0
	elif n == 1 or n == 2:
		return 1
	else:
		for j in range(2, int(sqrt(n)) + 1):
			if n % j == 0:
				return j
		return 1
t = int(input())
for i in range(t):
	n = int(input())
	s = isPrime(n)
	if s == 1:
		print(s + n)
	else:
		print(n + n // s)


from math import sqrt

def primes(n):
	x = []
	if n % 2 == 0:
		x += [2]
		while n % 2 == 0:
			n //= 2
	if n % 3 == 0:
		x += [3]
		while n % 3 == 0:
			n //= 3
	if n % 5 == 0:
		x += [5]
		while n % 5 == 0:
			n //= 5
	for i in range(7, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			x += [i]
			while n % i == 0:
				n //= i
		if len(x) >= 2:
			return x
	if n > 2:
		x += [n]
	return x
for _ in range(int(input())):
	n = int(input())
	x = primes(n)
	if len(x) == 1 and x[0] == n:
		print(n + 1)
	else:
		print(n + n // x[0])


array_of_primes = []
prime = [True for i in range(10 ** 6 + 1)]
p = 2
while p * p <= 10 ** 6:
	if prime[p] == True:
		for i in range(p * p, 10 ** 6 + 1, p):
			prime[i] = False
	p += 1
for p in range(2, 10 ** 6 + 1):
	if prime[p]:
		array_of_primes.append(p)

def factorizer(n):
	primes = []
	indices = []
	last_index = 0
	j = 0
	p = array_of_primes[j]
	first_index = -1
	while p <= int(n ** 0.5) + 1:
		alpha = 0
		while n % p == 0:
			alpha += 1
			n = n // p
		if alpha != 0:
			primes.append(p)
			indices.append(alpha)
			if first_index == -1:
				first_index = j
		j += 1
		if j != 78498:
			p = array_of_primes[j]
		else:
			break
	if n != 1:
		primes.append(n)
		indices.append(1)
	return (primes, indices, first_index)
T = int(input())
for i in range(T):
	N = int(input())
	(primes, indices, first_index) = factorizer(N)
	x = N // primes[0]
	x = x * (primes[0] + 1)
	print(x)


import sys
from collections import deque
import heapq
import bisect
import math
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	n = cin()
	mini = float('inf')
	ans = -1
	x = 0
	if n % 2 != 0:
		x = n + 1
		docheck = abs(x * n) - 1
		ind = 1
		for i in range(1, int(math.sqrt(n)) + 1):
			if n % i == 0:
				if n // i == i and i != n:
					ind = max(ind, i)
				else:
					if i != n:
						ind = max(ind, i)
					if n // i != n:
						ind = max(ind, n // i)
		lowball = ind
		low = math.gcd(n, n + lowball)
		lcm = n * (n + lowball) // low
		check = abs(lcm - low)
		if docheck > check:
			x = n + lowball
	else:
		x = x + n // 2
		x += n
	print(x)
	return
for _ in range(test_case):
	ans()


import math
LCM = lambda x, y: x * y // math.gcd(x, y)
for _ in range(int(input())):
	n1 = int(input())
	p1 = 1
	curr = 10 ** 20
	output = (n1, n1 + 1)
	while p1 * p1 <= n1:
		if n1 % p1 == 0:
			f1 = abs(LCM(n1, n1 + p1) - math.gcd(n1, n1 + p1))
			f2 = f1 + 1
			if n1 + n1 // p1 != 2 * n1:
				f2 = abs(LCM(n1, n1 + n1 // p1) - math.gcd(n1, n1 + n1 // p1))
			cpl = (n1, n1 + p1)
			if f2 <= f1:
				cpl = (n1, n1 + n1 // p1)
			flag = min(f1, f2)
			if flag <= curr:
				output = cpl
				curr = min(curr, flag)
		p1 += 1
	print(output[1])


import math
compute_lcm = lambda x, y: x * y // math.gcd(x, y)
t = int(input())
for t_itr in range(t):
	n = int(input())
	p = 1
	cur_min = 10 ** 20
	res = (n, n + 1)
	while p * p <= n:
		if n % p == 0:
			fg1 = abs(compute_lcm(n, n + p) - math.gcd(n, n + p))
			fg2 = fg1 + 1
			if n + n // p != 2 * n:
				fg2 = abs(compute_lcm(n, n + n // p) - math.gcd(n, n + n // p))
			cpl = (n, n + p)
			if fg2 <= fg1:
				cpl = (n, n + n // p)
			flag = min(fg1, fg2)
			if flag <= cur_min:
				res = cpl
				cur_min = min(cur_min, flag)
		p += 1
	print(res[1])


t = int(input())
maxn = -1
ips = []
for tt in range(t):
	N = int(input())
	ips.append(N)
	if N > maxn:
		maxn = N
nn = min(maxn, 1000000)
prime = [True] * (nn + 1)
p = 2
while p * p <= nn:
	if prime[p] == True:
		i = p * 2
		while i <= nn:
			prime[i] = False
			i += p
	p += 1
for ip in ips:
	if ip < nn and prime[ip]:
		print(ip + 1)
	else:
		flag = 1
		for p in range(2, min(ip // 2 + 1, nn + 1)):
			if prime[p]:
				if ip % p == 0:
					print(ip + ip // p)
					flag = 0
					break
		if flag:
			if flag:
				print(ip + 1)


import math
compute_lcm = lambda x1, y1: x1 * y1 // math.gcd(x1, y1)
t = int(input())
for t_itr in range(t):
	n1 = int(input())
	p1 = 1
	current_min = 10 ** 20
	out = (n1, n1 + 1)
	while p1 * p1 <= n1:
		if n1 % p1 == 0:
			flag1 = abs(compute_lcm(n1, n1 + p1) - math.gcd(n1, n1 + p1))
			flag2 = flag1 + 1
			if n1 + n1 // p1 != 2 * n1:
				flag2 = abs(compute_lcm(n1, n1 + n1 // p1) - math.gcd(n1, n1 + n1 // p1))
			cpl = (n1, n1 + p1)
			if flag2 <= flag1:
				cpl = (n1, n1 + n1 // p1)
			flag = min(flag1, flag2)
			if flag <= current_min:
				out = cpl
				current_min = min(current_min, flag)
		p1 += 1
	print(out[1])


def isPrime(n):
	if n == 1:
		return 0
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 0
		i += 1
	return 1
for i in range(int(input())):
	n = int(input())
	if isPrime(n):
		print(n + 1)
		continue
	j = 2
	while j * j <= n:
		if n % j == 0:
			print(n // j + n)
			break
		j += 1


import math
t = int(input())
for j in range(0, t):
	n = int(input())
	prime_flag = 0
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			prime_flag = 1
			m = i
			break
	if prime_flag == 0:
		q = math.gcd(n, n + 1)
		print(n + 1)
	else:
		w = n // m * (m + 1)
		print(w)