The $\text{$gcdSum$}$ of a positive integer is the $gcd$ of that integer with its sum of digits. Formally, $\text{$gcdSum$}(x) = gcd(x, \text{ sum of digits of } x)$ for a positive integer $x$. $gcd(a, b)$ denotes the greatest common divisor of $a$ and $b$ — the largest integer $d$ such that both integers $a$ and $b$ are divisible by $d$.

For example: $\text{$gcdSum$}(762) = gcd(762, 7 + 6 + 2)=gcd(762,15) = 3$.

Given an integer $n$, find the smallest integer $x \ge n$ such that $\text{$gcdSum$}(x) > 1$.


-----Input-----

The first line of input contains one integer $t$ $(1 \le t \le 10^4)$ — the number of test cases.

Then $t$ lines follow, each containing a single integer $n$ $(1 \le n \le 10^{18})$.

All test cases in one test are different.


-----Output-----

Output $t$ lines, where the $i$-th line is a single integer containing the answer to the $i$-th test case.


-----Examples-----

Input
3
11
31
75
Output
12
33
75


-----Note-----

Let us explain the three test cases in the sample.

Test case 1: $n = 11$:

$\text{$gcdSum$}(11) = gcd(11, 1 + 1) = gcd(11,\ 2) = 1$.

$\text{$gcdSum$}(12) = gcd(12, 1 + 2) = gcd(12,\ 3) = 3$.

So the smallest number $\ge 11$ whose $gcdSum$ $> 1$ is $12$.

Test case 2: $n = 31$:

$\text{$gcdSum$}(31) = gcd(31, 3 + 1) = gcd(31,\ 4) = 1$.

$\text{$gcdSum$}(32) = gcd(32, 3 + 2) = gcd(32,\ 5) = 1$.

$\text{$gcdSum$}(33) = gcd(33, 3 + 3) = gcd(33,\ 6) = 3$.

So the smallest number $\ge 31$ whose $gcdSum$ $> 1$ is $33$.

Test case 3: $\ n = 75$:

$\text{$gcdSum$}(75) = gcd(75, 7 + 5) = gcd(75,\ 12) = 3$.

The $\text{$gcdSum$}$ of $75$ is already $> 1$. Hence, it is the answer.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Complete search


Solutions:
def gcd(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	k = 0
	while (a | b) & 1 == 0:
		a = a >> 1
		b = b >> 1
		k = k + 1
	while a & 1 == 0:
		a = a >> 1
	while b != 0:
		while b & 1 == 0:
			b = b >> 1
		if a > b:
			temp = a
			a = b
			b = temp
		b = b - a
	return a << k
T = int(input())
for t in range(T):
	n = int(input())
	x = n
	s = 0
	while x:
		s += x % 10
		x = x // 10
	while gcd(n, s) <= 1:
		n += 1
		x = n
		s = 0
		while x:
			s += x % 10
			x = x // 10
	print(n)


import math
t = int(input())

def getSum(p):
	sum = 0
	for digit in str(p):
		sum += int(digit)
	return sum

def sum_gcd(e, f):
	return math.gcd(e, f)
for _ in range(t):
	n = int(input())
	chk = sum_gcd(n, getSum(n))
	while chk == 1:
		n += 1
		chk = sum_gcd(n, getSum(n))
	print(n)


import sys

def gcd(a, b):
	return gcd(b, a % b) if b else a
input()
for n in sys.stdin.read().split():
	i = int(n)
	while gcd(i, sum(map(int, list(str(i))))) <= 1:
		i += 1
	print(i)


import math

def sum(x):
	s = 0
	while x > 0:
		s += x % 10
		x = x // 10
	return s
t = int(input())
for i in range(t):
	n = int(input())
	if math.gcd(n, sum(n)) > 1:
		print(n)
	elif math.gcd(n + 1, sum(n + 1)) > 1:
		print(n + 1)
	else:
		print(n + 2)


from math import gcd
inp = int(input())
outp = []

def findSumNum(x):
	a = 0
	while x != 0:
		a += x % 10
		x //= 10
	return a
for i in range(inp):
	g = int(input())
	l = g
	while gcd(l, findSumNum(l)) == 1:
		l += 1
	outp.append(l)
for i in range(len(outp)):
	print(outp[i])


from math import gcd
for _ in range(int(input())):
	n = int(input())
	sum_n = sum([int(i) for i in str(n)])
	while gcd(n, sum_n) == 1:
		n += 1
		sum_n = sum([int(i) for i in str(n)])
	print(n)


from math import gcd

def sum_of_digits(x):
	x = str(x)
	sm = 0
	for i in x:
		sm += int(i)
	return sm
for _ in range(int(input())):
	n = int(input())
	flag = 0
	while True:
		sod = sum_of_digits(n)
		reqgcd = gcd(sod, n)
		if reqgcd > 1:
			flag = n
			break
		else:
			n += 1
	if flag > 1:
		print(flag)


import math

def sod(n):
	s = 0
	while n != 0:
		d = n % 10
		s = s + d
		n = n // 10
	return s
for _ in range(int(input())):
	n = int(input())
	while n:
		s = sod(n)
		x = math.gcd(n, s)
		if x > 1:
			print(n)
			break
		n += 1


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
list1 = []
for i in range(int(input())):
	a = int(input())
	if a % 3 == 0:
		list1.append(a)
	elif a % 3 == 2:
		if gcd(sum(map(lambda x: int(x), list(str(a)))), a) > 1:
			list1.append(a)
		else:
			list1.append(a + 1)
	elif gcd(sum(map(lambda x: int(x), list(str(a)))), a) > 1:
		list1.append(a)
	elif gcd(sum(map(lambda x: int(x), list(str(a + 1)))), a + 1) > 1:
		list1.append(a + 1)
	else:
		list1.append(a + 2)
print(*list1, sep='\n')


import math
import sys

def read_a_num(line):
	[n] = list(map(int, line.strip().split(' ')))
	return n

def gcdsum(n):
	s = 0
	for d in str(n):
		s += int(d)
	return math.gcd(n, s)
lines = sys.stdin.readlines()
t = read_a_num(lines[0])
for line in lines[1:t + 1]:
	n = read_a_num(line)
	while True:
		res = gcdsum(n)
		if res > 1:
			print(n)
			break
		n += 1


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	s = input()
	x = int(s)
	s = sum([int(i) for i in s])
	while gcd(x, s) == 1:
		x += 1
		s = sum([int(i) for i in str(x)])
	print(x)


import math
for _ in range(int(input())):
	n = input()
	n2 = 0
	for i in range(len(n)):
		n2 += int(n[i])
	a = math.gcd(max(int(n), n2), min(int(n), n2))
	n3 = int(n)
	if a <= 1:
		n3 = str(int(n) + 1)
		n4 = 0
		for i in range(len(n3)):
			n4 += int(n3[i])
		b = math.gcd(max(int(n3), n4), min(int(n3), n4))
		n4 = 0
		while b <= 1:
			n3 = str(int(n3) + 1)
			for i in range(len(n3)):
				n4 += int(n3[i])
			b = math.gcd(max(int(n3), n4), min(int(n3), n4))
	print(n3)


import sys
import math

def check(x):
	return math.gcd(x, sum([ord(c) - ord('0') for c in str(x)])) != 1
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	while not check(n):
		n += 1
	print(n)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	g = gcd(n, sum(list(map(int, list(str(n))))))
	while g <= 1:
		n += 1
		g = gcd(n, sum(list(map(int, list(str(n))))))
	print(n)


import math

def digitsum(n):
	u = 0
	while n > 0:
		r = n % 10
		n = n // 10
		u += r
	return u
s = []
for i in range(int(input())):
	n = int(input())
	while math.gcd(n, digitsum(n)) == 1:
		n += 1
	s.append(n)
for i in range(len(s)):
	print(s[i])


from sys import stdin
from sys import stdout
from math import gcd
try:
	(stdin, stdout) = (open('input.txt', 'r'), open('out.txt', 'w'))
except:
	pass
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	for i in range(n, n + 100):
		if gcd(i, sum(list(map(int, str(i))))) > 1:
			stdout.write(str(i) + '\n')
			break


from math import gcd

def sum_of_digits(i):
	s = 0
	while i > 0:
		s += i % 10
		i = i // 10
	return s
t = int(input())
arr = []
for _ in range(t):
	arr.append(int(input()))
for (i, x) in enumerate(arr):
	while True:
		p = gcd(x, sum_of_digits(x))
		if p > 1:
			print(x)
			break
		else:
			x += 1


import math
T = int(input())
tab = [int(input()) for _ in range(T)]
res = []

def get_sum(number):
	s = str(number)
	res = 0
	for elem in s:
		res += int(elem)
	return res

def process(number):
	while True:
		tmp = math.gcd(number, get_sum(number))
		if tmp > 1:
			return number
		number += 1
for elem in tab:
	print(process(elem))


from math import *
for u in range(int(input())):
	n = int(input())
	s = sum(map(int, str(n)))
	if gcd(n, s) > 1:
		print(n)
	else:
		f = 0
		while 1:
			n += 1
			s = sum(map(int, str(n)))
			if gcd(n, s) > 1:
				f = 1
				break
		print(n)


def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
T = int(input())
for i in range(T):
	x = input()
	flag = True
	while flag != False:
		if computeGCD(int(x), sum([int(i) for i in x])) > 1:
			print(x)
			flag = False
		else:
			x = str(int(x) + 1)


import math
from collections import Counter
import bisect

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

def d(n):
	s = 0
	while n:
		s += n % 10
		n = n // 10
	return s
for _ in range(int(input())):
	n = int(input())
	while True:
		if gcd(n, d(n)) > 1:
			break
		n = n + 1
	print(n)


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

def sumgcd(a):
	a = int(n)
	b = sum([int(i) for i in n])
	return gcd(a, b)
for tc in range(int(input())):
	n = input()
	t = sumgcd(n)
	while t <= 1:
		n = str(int(n) + 1)
		t = sumgcd(n)
	print(n)


from math import gcd

def gcdSum(x):
	while True:
		sum_digits = sumDigits(x)
		res = gcd(x, sum_digits)
		if res > 1:
			break
		x += 1
	return x

def sumDigits(x):
	sm = 0
	while x != 0:
		(q, r) = divmod(x, 10)
		sm += r
		x = q
	return sm

def testcases():
	tests = [11, 31, 75]
	for test in tests:
		res = gcdSum(test)
		print(f'test={test!r}, res={res!r}')

def main():
	testcases = int(input())
	tests = []
	for test in range(testcases):
		tests.append(int(input()))
	for num in tests:
		print(gcdSum(num))
main()


import sys
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def get_int():
	return int(input())

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

def get_char_list():
	s = input()
	return list(s[:len(s) - 1])

def get_tuple_ints():
	return tuple(map(int, input().split()))

def print_iterable(p):
	print(' '.join(map(str, p)))
import math
from math import gcd

def main():
	t = get_int()
	for i in range(t):
		n = get_int()
		while n > 0:
			n1 = n
			sum = 0
			while n1 != 0:
				sum += n1 % 10
				n1 = n1 // 10
			if gcd(n, sum) != 1:
				print(n)
				break
			else:
				n += 1
main()


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	n = int(input())
	while True:
		n = n
		s = list(str(n))
		temp = sum([int(s[i]) for i in range(len(s))])
		if gcd(n, temp) > 1:
			print(n)
			break
		n += 1


import math

def sumOfDigits(n):
	res = 0
	n = str(n)
	for i in range(len(n)):
		res += int(n[i])
	return res

def getGCD(a, b):
	return math.gcd(a, b)

def solve(n):
	while True:
		if getGCD(n, sumOfDigits(n)) == 1:
			n += 1
		else:
			break
	return n
t = int(input())
for i in range(t):
	n = int(input())
	ans = solve(n)
	print(ans)


from math import *

def sm(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s

def gs(n):
	return gcd(n, sm(n))
for t in range(int(input())):
	n = int(input())
	while gs(n) == 1:
		n += 1
	print(n)


def gcd(n1, n2):
	if n2 == 0:
		return n1
	return gcd(n2, n1 % n2)

def check(s):
	n = int(s)
	sun = 0
	for i in s:
		sun += int(i)
	ans = gcd(n, sun)
	if ans > 1:
		print(n)
	else:
		a = int(s)
		s = str(a + 1)
		check(s)
t = int(input())
for _ in range(t):
	s = input()
	check(s)


import math
y = int(input())
for i in range(1, y + 1):
	n = int(input())
	j = n
	while n >= j:
		t = n
		sum = 0
		while n:
			r = n % 10
			sum += r
			n = n // 10
		n = t
		a = math.gcd(n, sum)
		if a > 1:
			print(n)
			break
		else:
			n = n + 1


import math
list1 = []

def sum_number(x):
	ans = 0
	while x > 0:
		remainder = x % 10
		ans += remainder
		x = x // 10
	return ans

def gcdsum(x):
	return math.gcd(sum_number(x), x)
t = int(input())
for n in range(t):
	x = int(input())
	while gcdsum(x) == 1:
		x += 1
	list1.append(x)
for z in list1:
	print(z)


rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
from math import gcd
for _ in range(rn()):
	n = rn()

	def f(n):
		ans = 0
		for i in str(n):
			ans += int(i)
		return ans
	while gcd(n, f(n)) == 1:
		n += 1
	print(n)


import math
z = []
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in str(n)]
	b = sum(a)
	c = math.gcd(n, b)
	while c <= 1:
		n = n + 1
		a = [int(i) for i in str(n)]
		b = sum(a)
		c = math.gcd(n, b)
	z.append(n)
print(*z, sep='\n')


def getSum(n):
	sum = 0
	while n != 0:
		sum = sum + n % 10
		n = n // 10
	return sum

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

def solve(num):
	s = getSum(num)
	gcd = computeGCD(num, s)
	if gcd == 1:
		solve(num + 1)
	else:
		print(num)
t = int(input())
for i in range(t):
	num = int(input())
	solve(num)


import math
import os
import sys
from collections import Counter
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	for _ in range(int(input())):
		n = int(input())
		i = n
		while True:
			a = str(i)
			s = 0
			for j in a:
				s += int(j)
			if math.gcd(i, s) > 1:
				print(i)
				break
			i += 1
main()


import math

def get_digits(n):
	return [int(i) for i in list(str(n))]

def find_ans(n):
	i = n
	while True:
		digits = get_digits(i)
		if math.gcd(i, sum(digits)) > 1:
			return i
		i += 1
test_cases = int(input())
ans = []
for i in range(test_cases):
	n = int(input())
	ans.append(find_ans(n))
for i in ans:
	print(i)


from math import gcd
for _ in range(int(input())):
	num = input()
	a = int(num)
	b = sum((int(x) for x in num))
	while gcd(a, b) == 1:
		a += 1
		b = sum((int(x) for x in str(a)))
	print(a)


import math

def digsum(n):
	n = str(n)
	s = 0
	for i in n:
		s += int(i)
	return s
for _ in range(int(input())):
	n = int(input())
	for i in range(n, 10 ** 19):
		if math.gcd(i, digsum(i)) > 1:
			print(i)
			break


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
a = int(input())
i = 0
while i < a:
	i += 1
	t = int(input())
	while True:
		n = str(t)
		sum = 0
		for j in n:
			sum += int(j)
		b = gcd(t, sum)
		if b > 1:
			print(t)
			break
		else:
			t += b


def gcd(num, num2):
	smaller = min(num, num2)
	larger = max(num, num2)
	for div in range(smaller, 0, -1):
		if smaller % div == 0 and larger % div == 0:
			return div

def gcd_sum(n):
	n -= 1
	while True:
		n += 1
		stringN = str(n)
		total = 0
		for digit in stringN:
			total += int(digit)
		gcdSum = gcd(n, total)
		if gcdSum > 1:
			return n
for i in range(int(input())):
	print(gcd_sum(int(input())))


import math
for i in range(int(input())):
	n = int(input())
	k = 1
	while True:
		k = math.gcd(n, sum(map(int, str(n))))
		if k != 1:
			break
		else:
			n += 1
	print(n)


import sys
import math
input = sys.stdin.readline

def gcd_sum():
	suma = 0
	for i in str(n):
		suma += int(i)
	return math.gcd(suma, n)
for test in range(int(input())):
	n = int(input())
	while gcd_sum() == 1:
		n += 1
	print(n)


from pprint import pprint
import sys
input = sys.stdin.readline

def do():
	import math

	def ddd(num):
		total = 0
		s = list(str(num))
		for x in s:
			total += int(x)
		return math.gcd(num, total)
	n = int(input())
	while True:
		if ddd(n) == 1:
			n += 1
			continue
		break
	print(n)
q = int(input())
for _ in range(q):
	do()


import sys
from math import *
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())

def total(n):
	n = str(n)
	tot = 0
	for i in n:
		tot += int(i)
	return (int(n), tot)

def solve(n):
	while 1:
		(num, tot) = total(n)
		if gcd(num, tot) > 1:
			print(num)
			break
		else:
			n += 1
for _ in range(int(input())):
	n = int(input())
	solve(n)


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

def sum1(a):
	s = 0
	while a > 0:
		r = a % 10
		s = s + r
		a = a // 10
	return s
for _ in range(int(input())):
	n = int(input())
	while True:
		b = sum1(n)
		c = hcf(n, b)
		if c > 1:
			print(n)
			break
		else:
			n = n + 1


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

def sumdigit(n):
	ans = 0
	while n != 0:
		ans += n % 10
		n = n // 10
	return ans
for t in range(int(input())):
	n = int(input())
	while 1:
		if gcd(n, sumdigit(n)) > 1:
			print(n)
			break
		n += 1


import sys, io, os, math
from math import ceil, log, gcd, sqrt, floor
from itertools import permutations
import operator
mod = 1000000007
mod1 = 998244353

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

def strinp():
	return sys.stdin.readline()

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

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

def flush():
	return stdout.flush()

def power_two(x):
	return 1 << x

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

def power(a, n):
	res = 1
	while n:
		if n & 1:
			res = res % mod * a % mod % mod
			n -= 1
		else:
			a = a % mod * a % mod % mod
			n = n // 2
	return res

def calc(n):
	s = 0
	for i in str(n):
		s += int(i)
	return s

def solve():
	n = intinp()
	s = calc(n)
	while gcd(s, n) <= 1:
		n += 1
		s = calc(n)
	print(n)

def main():
	tc = intinp()
	while tc:
		solve()
		tc -= 1
main()


import sys

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_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

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

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

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

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize
from math import gcd

def solve():
	for _ in range(get_int()):
		n = get_int()
		while True:
			x = n
			summ = 0
			while x:
				summ += x % 10
				x //= 10
			g = gcd(n, summ)
			if g > 1:
				get_print_int(n)
				break
			n += 1
solve()


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import sys
import copy

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

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

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

def sumi(n):
	s = 0
	while n > 0:
		s += n % 10
		n = n // 10
	return s
for _ in range(int(input())):
	n = int(input())
	while True:
		if gcd(n, sumi(n)) > 1:
			print(n)
			break
		n += 1


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

def getb(a):
	sum = 0
	str_a = str(a)
	for c in str_a:
		sum += ord(c) - ord('0')
	return sum
t = input()
for _ in range(int(t)):
	a = int(input())
	ans = gcd(a, getb(a))
	while ans == 1:
		a += 1
		ans = gcd(a, getb(a))
	print(a)


import math

def f(n):
	return sum((int(i) for i in str(n)))
for _ in range(int(input())):
	n = int(input())
	while 1:
		if math.gcd(n, f(n)) > 1:
			print(n)
			break
		n += 1


import math

def gcds(x):
	n = x
	s = 0
	while n > 0:
		s += n % 10
		n = n // 10
	return math.gcd(x, s)
t = int(input())
for _ in range(t):
	num = int(input())
	while 1:
		if gcds(num) > 1:
			print(num)
			break
		else:
			num += 1


for _ in range(int(input())):
	a = int(input())
	temp = a
	ans = 0

	def sumer(s):
		an = 0
		while s != 0:
			an += s % 10
			s //= 10
		return an
	c = 0
	for i in range(10 + 1):
		ans = sumer(i + a)
		temp = i + a
		for j in range(ans, 0, -1):
			if ans % j == 0 and temp % j == 0:
				if j > 1:
					print(temp)
					c = 1
					break
		if c == 1:
			break


from math import gcd
t = int(input())
for i in range(t):
	n = int(input())
	x = n
	while gcd(x, sum((int(j) for j in str(x)))) == 1:
		x += 1
	print(x)


def gcdsum(a):
	answer = a
	num = 0
	k = str(a)
	b = []
	for i in k:
		b.append(int(i))
	for i in b:
		num += i
	while num != 0:
		(a, num) = (num, a % num)
	if a > 1:
		return answer
	else:
		return gcdsum(answer + 1)
for _ in range(int(input())):
	a = int(input())
	print(gcdsum(a))


from math import gcd
for _ in range(int(input())):
	n = input()
	s = sum(map(int, n.strip()))
	n = int(n)
	while gcd(n, s) <= 1:
		n += 1
		s = sum(map(int, str(n).strip()))
	print(n)


import math

def s(n):
	n = str(n)
	s = 0
	for j in n:
		s = s + int(j)
	return s
t = int(input())
for i in range(0, t, 1):
	n = input()
	n = int(n)
	p = math.gcd(n, s(n))
	if p > 1:
		print(n)
	else:
		while p <= 1:
			n = n + 1
			p = math.gcd(n, s(n))
		print(n)


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

def sum(n):
	r = 0
	while n > 0:
		r += n % 10
		n = n // 10
	return r
for _ in range(int(input())):
	n = int(input())
	while True:
		s = sum(n)
		if GCD(n, s) > 1:
			print(n)
			break
		else:
			n += 1


from math import gcd

def sm(x):
	s = 0
	while x:
		s += x % 10
		x //= 10
	return s
for t in range(int(input())):
	n = int(input())
	for i in range(3):
		s = sm(n)
		if gcd(n, s) > 1:
			print(n)
			break
		n += 1


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	i = n
	while True:
		l = list(map(int, str(i).strip()))
		if gcd(i, sum(l)) > 1:
			print(i)
			break
		else:
			i = i + 1


def sumOfDigits(n):
	sol = 0
	while n > 0:
		sol += n % 10
		n //= 10
	return sol

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for t in range(int(input())):
	n = int(input())
	while gcd(n, sumOfDigits(n)) == 1:
		n += 1
	print(n)


def main():
	from sys import stdin, stdout
	from math import gcd
	rl = stdin.readline
	wl = stdout.write
	for _ in range(int(rl())):
		i = int(rl())
		while i % 3 != 0 and gcd(i, sum((int(x) for x in str(i)))) == 1:
			i += 1
		wl(str(i) + '\n')
main()


from math import gcd

def get_sum(m):
	c = 0
	while m > 0:
		c += m % 10
		m //= 10
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	s = get_sum(n)
	g = gcd(n, s)
	while g == 1:
		n += 1
		s = get_sum(n)
		g = gcd(n, s)
	print(n)


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

def gcdsum(m):
	s = 0
	while m:
		s += m % 10
		m //= 10
	return s
test = int(input())
for t in range(test):
	n = int(input())
	while gcd(n, gcdsum(n)) == 1:
		n += 1
	print(n)


import math

def tot(n):
	s = 0
	while n > 0:
		s += n % 10
		n = n // 10
	return s
t = int(input())
for _ in range(t):
	n = int(input())
	while True:
		if math.gcd(n, tot(n)) > 1:
			print(n)
			break
		n += 1


import math

def getsum(n):
	s = 0
	for i in n:
		s += int(i)
	return s

def gcd(a, n):
	p = math.gcd(a, n)
	return p
n = int(input())
a = []
for i in range(0, n):
	p = int(input())
	a.append(p)
for i in range(0, n):
	p = 1
	l = a[i]
	while p == 1:
		s = getsum(str(l))
		p = gcd(l, s)
		l += 1
	print(l - 1)


import sys
import math

def solve():
	return None

def main():
	q = []
	for line in sys.stdin.readlines():
		q.append(line)
	for i in range(len(q)):
		q[i] = q[i].rstrip().split(' ')
	for i in range(1, len(q)):
		n = int(q[i][0])
		x = q[i][0]
		flag = 0
		while flag == 0:
			s = 0
			for i in x:
				s += int(i)
			if math.gcd(n, s) > 1:
				print(n)
				flag = 1
			else:
				n += 1
				x = str(n)
main()


import sys
import math

def check(x):
	ans = 0
	while x > 0:
		ans += x % 10
		x = x // 10
	return ans
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	while True:
		y = check(n)
		if math.gcd(y, n) > 1:
			print(n)
			break
		n += 1


import math

def sumdig(n):
	res = 0
	while n > 0:
		tmp = n % 10
		res += tmp
		n = n // 10
	return res
for _ in range(int(input())):
	n = int(input())
	s = sumdig(n)
	while True:
		if n % 10 == 0:
			s = sumdig(n)
		tmp = math.gcd(n, s)
		if tmp > 1:
			print(n)
			break
		n += 1
		s += 1


try:
	import math

	def sumz(a):
		res = 0
		while a != 0:
			res = res + a % 10
			a = a // 10
		return res
	for _ in range(int(input())):
		n = int(input())
		if n == 0:
			n += 1
		while n:
			if math.gcd(n, sumz(n)) > 1:
				print(n)
				break
			else:
				n = n + 1
except:
	pass


import math

def su(n):
	s = 0
	while n > 0:
		r = n % 10
		s = s + r
		n = n // 10
	return s
t = int(input())
for i in range(t):
	n = int(input())
	s = su(n)
	g = math.gcd(n, s)
	if g > 1:
		print(n)
	else:
		j = n + 1
		while g <= 1:
			s = su(j)
			g = math.gcd(j, s)
			j = j + 1
		print(j - 1)


def _gcd(a, b):
	if b == 0:
		return a
	else:
		return _gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	a = 1
	while True:
		l = list(str(n))
		l = list(map(int, l))
		s = sum(l)
		a = _gcd(n, s)
		if a > 1:
			break
		n += 1
	print(n)


import math
for s in [*open(0)][1:]:
	n = int(s)
	while math.gcd(n, sum(map(int, str(n)))) < 2:
		n += 1
	print(n)


T_ON = 1
DEBUG_ON = 0
MOD = 998244353

def solve():
	n = read_int()
	x = n
	while True:
		y = 0
		for c in str(x):
			y += int(c)
		if gcd(x, y) > 1:
			print(x)
			return
		x += 1

def main():
	T = read_int() if T_ON else 1
	for i in range(T):
		solve()

def debug(*xargs):
	if DEBUG_ON:
		print(*xargs)
from collections import *
import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int():
	return int(input())

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

def print_nums(nums):
	print(' '.join(map(str, nums)))

def YES():
	print('YES')

def Yes():
	print('Yes')

def NO():
	print('NO')

def No():
	print('No')

def First():
	print('First')

def Second():
	print('Second')

def fib(n):
	(a, b) = (0, 1)
	for _ in range(n):
		(a, b) = (b, a + b)
	return a

def fib_ns(n):
	assert n >= 1
	f = [0 for _ in range(n + 1)]
	f[0] = 0
	f[1] = 1
	for i in range(2, n + 1):
		f[i] = f[i - 1] + f[i - 2]
	return f

def fib_to_n(n):
	f = []
	(a, b) = (0, 1)
	while a <= n:
		f.append(a)
		(a, b) = (b, a + b)
	return f

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

def xgcd(a, b):
	(x0, x1, y0, y1) = (0, 1, 1, 0)
	while a != 0:
		((q, a), b) = (divmod(b, a), a)
		(y0, y1) = (y1, y0 - q * y1)
		(x0, x1) = (x1, x0 - q * x1)
	return (b, x0, y0)

def lcm(a, b):
	d = gcd(a, b)
	return a * b // d

def is_even(x):
	return x % 2 == 0

def is_odd(x):
	return x % 2 == 1

def modinv(a, m):
	(g, x, _) = xgcd(a, m)
	if g != 1:
		raise Exception('gcd(a, m) != 1')
	return x % m

def mod_add(x, y):
	x += y
	while x >= MOD:
		x -= MOD
	while x < 0:
		x += MOD
	return x

def mod_mul(x, y):
	return x * y % MOD

def mod_pow(x, y):
	if y == 0:
		return 1
	if y % 2:
		return mod_mul(x, mod_pow(x, y - 1))
	p = mod_pow(x, y // 2)
	return mod_mul(p, p)

def mod_inv(y):
	return mod_pow(y, MOD - 2)

def mod_div(x, y):
	return mod_mul(x, mod_inv(y))

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

def gen_primes(n):
	P = [True for _ in range(n + 1)]
	P[0] = P[1] = False
	for i in range(int(n ** 0.5) + 1):
		if P[i]:
			for j in range(2 * i, n + 1, i):
				P[j] = False
	return P

def is_lucky(n):
	return set(list(str(n))).issubset({'4', '7'})
main()


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	n = int(input())
	t = n
	while True:
		k = t
		ase = 0
		while k > 0:
			ase += k % 10
			k //= 10
		if math.gcd(ase, t) > 1:
			print(t)
			break
		t += 1


from math import *
from math import factorial as fact, comb as ncr
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
li = lambda : list(map(int, input().split()))
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def gcdsum(n):
	s = sum((int(x) for x in str(n)))
	return gcd(n, s)

def solve():
	for _ in range(int(input())):
		n = int(input())
		if gcdsum(n) > 1:
			print(n)
		elif gcdsum(n + 1) > 1:
			print(n + 1)
		else:
			print(n + 2)
solve()


import sys
get_string = lambda : sys.stdin.readline().strip()
get_intmap = lambda : map(int, get_string().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for t in range(int(get_string())):
	n = int(get_string())
	x = n
	while True:
		sum_of_digits = sum([int(i) for i in str(x)])
		if gcd(x, sum_of_digits) > 1:
			print(x)
			break
		x += 1


import sys
input = sys.stdin.readline
ans_dict = {}

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while a % b != 0:
		(a, b) = (b, a % b)
	return b
for _ in range(int(input())):
	num_real = int(input())
	num = num_real
	while True:
		if num in ans_dict:
			print(ans_dict[num])
			break
		num_tmp = num
		num_digit_sum = 0
		while num_tmp > 0:
			num_digit_sum += num_tmp % 10
			num_tmp //= 10
		if gcd(num, num_digit_sum) > 1:
			print(num)
			ans_dict[num_real] = num
			break
		else:
			num += 1


from math import gcd

def gcdSum(num):
	x = num
	y = 0
	count = str(num)
	for i in count:
		y += int(i)
	return gcd(x, y)
t = int(input())
for i in range(t):
	n = int(input())
	while gcdSum(n) <= 1:
		n += 1
	print(n)


def gcd(num1, num2):
	if num1 == 0:
		return num2
	return gcd(num2 % num1, num1)

def g(n):
	s = 0
	for i in str(n):
		s += int(i)
	return s

def raf():
	n = int(input())
	i = 0
	while i <= 100:
		if gcd(g(n + i), n + i) > 1:
			print(n + i)
			return
		else:
			i += 1

def main():
	for _ in range(int(input())):
		raf()
main()


import math
for i in range(int(input())):
	n = int(input())
	while True:
		r = math.gcd(n, sum(map(lambda d: int(d), str(n))))
		if r > 1:
			print(n)
			break
		n += 1


import math
t = input()
t = int(t)
for x in range(t):
	n = input()
	for p in range(int(n), int(n) + 10000):
		n2 = 0
		p = str(p)
		for y in range(len(p)):
			n2 += int(p[y])
		if math.gcd(int(p), int(n2)) > 1:
			print(p)
			break


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

def answer(n):
	while True:
		m = str(n)
		sum1 = 0
		for i in m:
			sum1 += int(i)
		if compute_hcf(n, sum1) > 1:
			return n
		else:
			n += 1
t = int(input())
for w in range(t):
	n = int(input())
	print(answer(n))


def gcd_euclidean(a, b):
	m = max(a, b)
	n = min(a, b)
	r = m % n
	while r > 0:
		m = n
		n = r
		r = m % n
	return n
t = int(input())
for i in range(t):
	n = int(input())
	while True:
		sn = 0
		pn = n
		while pn > 0:
			sn += pn % 10
			pn = pn // 10
		result = gcd_euclidean(n, sn)
		if result > 1:
			break
		n += 1
	print(n)


from math import gcd

def sum_digits(n):
	r = 0
	while n:
		(r, n) = (r + n % 10, n // 10)
	return r
total_lines = int(input())
final_list = []
for item in range(total_lines):
	current = int(input())
	while True:
		sum_dig = sum_digits(current)
		if gcd(current, sum_dig) > 1:
			final_list.append(current)
			break
		current += 1
for x in final_list:
	print(x)


import math

def sum_digits(n):
	s = 0
	while n != 0:
		s += n % 10
		n = n // 10
	return s
t = int(input())
for _ in range(t):
	n = int(input())
	while math.gcd(sum_digits(n), n) == 1:
		n += 1
	print(n)


import math

def getSum(x):
	sum = 0
	while x != 0:
		sum = sum + x % 10
		x = x // 10
	return sum
import math
t = int(input())
for z in range(t):
	n = int(input())
	while math.gcd(getSum(n), n) <= 1:
		n = n + 1
	print(n)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for i in range(int(input())):
	n = int(input())
	while True:
		l = list(str(n))
		sum1 = 0
		for i in l:
			sum1 += int(i)
		if gcd(n, sum1) > 1:
			print(n)
			break
		n += 1


def hcfnaive(a, b):
	if b == 0:
		return a
	else:
		return hcfnaive(b, a % b)
for _ in range(int(input())):
	n = int(input())
	s = str(n)
	b = 0
	for i in s:
		b += int(i)
	ans = 1
	while ans == 1:
		ans = hcfnaive(n, b)
		n += 1
		s = str(n)
		b = 0
		for i in s:
			b += int(i)
	print(n - 1)


import math

def getsum(n):
	sum = 0
	for digit in str(n):
		sum += int(digit)
	return sum
for dcfvbhjkl in range(int(input())):
	n = int(input())
	while True:
		if math.gcd(n, getsum(n)) > 1:
			print(n)
			break
		n += 1


import sys
from math import gcd

def f(n):
	s = str(n)
	x = 0
	for i in range(len(s)):
		x = x + int(s[i])
	return x
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	s1 = f(n)
	s2 = f(n + 1)
	if gcd(s1, n) > 1:
		print(n)
	elif gcd(s2, n + 1) > 1:
		print(n + 1)
	else:
		print(n + 2)


def answer(n):
	for i in range(n, n + 11):
		total = sum_of_digits(i)
		g = gcd(i, total)
		if g > 1:
			return i

def sum_of_digits(n):
	a = 0
	s = str(n)
	for i in s:
		a += int(i)
	return a

def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	print(answer(n))


def sum_of_digits(x):
	sum = 0
	while x > 0:
		sum += x % 10
		x = x // 10
	return sum

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

def solve(n):
	if gcd(n, sum_of_digits(n)) == 1:
		return solve(n + 1)
	return n
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	print(solve(n))


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

	def gcd(n):
		r = math.gcd(n, ss(n))
		if r > 1:
			return n
		else:
			return gcd(n + 1)

	def ss(n):
		s = 0
		while n != 0:
			s += n % 10
			n = n // 10
		return int(s)
	x = int(input())
	n = x
	gcdsum = gcd(n)
	print(gcdsum)


import math

def Gcd(n):
	temp = n
	sum = 0
	while n > 0:
		sum = sum + n % 10
		n = n // 10
	if math.gcd(temp, sum) > 1:
		return temp
	else:
		return Gcd(temp + 1)
t = int(input())
arr = []
for i in range(0, t):
	ele = int(input())
	arr.append(ele)
for i in range(0, t):
	print(Gcd(arr[i]))


import math

def gcdsm(n):
	arr = list(str(n).strip())
	sm = 0
	for ele in arr:
		sm += int(ele)
	gcsm = math.gcd(n, sm)
	if gcsm > 1:
		print(n)
	else:
		gcdsm(n + 1)
t = int(input())
for _ in range(t):
	n = int(input())
	gcdsm(n)


import math
num = int(input())

def getSum(n):
	s = 0
	n = str(n)
	for ch in n:
		s += int(ch)
	return s
for i in range(num):
	n = int(input())
	gcd = 1
	while gcd == 1:
		s = getSum(n)
		gcd = math.gcd(n, s)
		if gcd == 1:
			n += 1
	print(n)


t = int(input())

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

def sumgcd(x):
	s = 0
	temp = x
	while temp:
		s += temp % 10
		temp = temp // 10
	val = gcd(x, s)
	if val > 1:
		return x
	else:
		return sumgcd(x + 1)
for i in range(t):
	p = int(input())
	print(sumgcd(p))


from math import gcd
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	while True:
		curr = 0
		for i in str(n):
			curr += int(i)
		if gcd(curr, n) > 1:
			print(n)
			break
		n += 1


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

def sod(a):
	sum = 0
	for ch in str(a):
		sum += int(ch)
	return sum

def solve():
	n = int(input())
	sum = sod(n)
	while gcd(n, sum) <= 1:
		n += 1
		sum = sod(n)
	print(n)

def main():
	tc = int(input())
	while tc > 0:
		solve()
		tc -= 1
main()


import math
test = int(input())
for i in range(test):
	aa = int(input())
	s11 = 0
	s22 = str(aa)
	for p in s22:
		s11 += int(p)
	r1 = math.gcd(aa, s11)
	while r1 <= 1:
		aa += 1
		s3 = 0
		for j in str(aa):
			s3 += int(j)
		r1 = math.gcd(aa, s3)
	print(aa)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	answer = 0
	while True:
		s = sum(list(map(int, str(n))))
		if gcd(n, s) > 1:
			answer = n
			break
		n += 1
	print(answer)


from math import gcd

def sum_of_digits(i):
	k = list(str(i))
	s = 0
	for j in k:
		s += int(j)
	return s
t = int(input())
arr = []
for _ in range(t):
	arr.append(int(input()))
for (i, x) in enumerate(arr):
	while True:
		p = gcd(x, sum_of_digits(x))
		if p > 1:
			arr[i] = str(x)
			break
		else:
			x += 1
print('\n'.join(arr))


from math import gcd
t = int(input())
for i in range(t):
	n = int(input())
	cnt = n
	while True:
		k = cnt
		sum = 0
		while k:
			sum = sum + k % 10
			k //= 10
		if gcd(sum, cnt) > 1:
			print(cnt)
			break
		else:
			cnt += 1


from collections import deque
import sys
inf = float('inf')
input = sys.stdin.readline
from math import gcd

def digits(n):
	ans = 0
	for i in str(n):
		ans += int(i)
	return ans
for _ in range(int(input())):
	n = int(input())
	while True:
		if gcd(n, digits(n)) > 1:
			break
		n += 1
	print(n)


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

def cal(n):
	a = 0
	for i in str(n):
		a += ord(i) - 48
	return gcd(a, n)
n = int(input())
for i in range(n):
	s = int(input())
	while True:
		a = cal(s)
		if a > 1:
			print(s)
			break
		s += 1


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

def fun(m):
	sum = 0
	while m > 0:
		sum += m % 10
		m = m // 10
	return sum
t = int(input())
for i in range(t):
	n = int(input())
	b = fun(n)
	while 1:
		res = gcd(n, b)
		if res > 1:
			break
		n += 1
		if n % 10 == 0:
			b = fun(n)
		else:
			b += 1
	print(n)


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

def answer(n):
	while 1:
		sum = 0
		for i in str(n):
			sum += int(i)
		if gcd(n, sum) > 1:
			return n
		n += 1
for T in range(int(input())):
	n = int(input())
	print(answer(n))


import math
t = int(input())
for i in range(t):
	n = int(input())
	while 1:
		v = n
		v1 = v
		sumofv = 0
		while v > 0:
			k = v % 10
			v = v // 10
			sumofv += k
		n += 1
		if math.gcd(v1, sumofv) > 1:
			print(v1)
			break


def sum(x):
	ans = 0
	while x > 0:
		ans += x % 10
		x //= 10
	return ans

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	n = int(input())
	if gcd(n, sum(n)) > 1:
		print(n)
	elif gcd(n + 1, sum(n + 1)) > 1:
		print(n + 1)
	else:
		print(n + 2)


from math import gcd

def fun(n):
	while True:
		s = 0
		for i in str(n):
			s += int(i)
		if gcd(s, n) > 1:
			return n
		n += 1
for _ in range(int(input())):
	print(fun(int(input())))


import sys
import math
from math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor, log
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2 ** 20)
N = 20005

def getSum(n):
	sum = 0
	for digit in str(n):
		sum += int(digit)
	return sum
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	isOk = True
	while isOk:
		if gcd(n, getSum(n)) != 1:
			isOk = False
		else:
			n += 1
	print(n)


answers = []

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

def solve(n):
	if n % 3 == 0:
		answers.append(n)
		return
	a = n
	b = n + 1
	c = n + 2
	t1 = str(a)
	tot1 = 0
	for ele in t1:
		tot1 += int(ele)
	final = gcd(a, tot1)
	if final > 1:
		answers.append(a)
		return
	t2 = str(b)
	tot2 = 0
	for ele in t2:
		tot2 += int(ele)
	final = gcd(b, tot2)
	if final > 1:
		answers.append(b)
		return
	else:
		answers.append(c)
		return
T = int(input())
while T:
	n = int(input())
	solve(n)
	T -= 1
for ans in answers:
	print(ans)


from math import gcd

def check(num):
	sm = sum(list(map(int, str(num))))
	if gcd(num, sm) > 1:
		return True
	return False
for t in range(int(input())):
	num = int(input())
	for i in range(num, num * 10):
		if check(i):
			print(i)
			break


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def sod(n):
	s = str(n)
	s1 = 0
	for i in s:
		s1 += int(i)
	return s1

def solve():
	for _ in range(ii()):
		n = ii()
		while True:
			x = sod(n)
			g = gcd(n, x)
			if g > 1:
				print(n)
				break
			n += 1
if file:
	if path.exists('tmp/input.txt'):
		sys.stdin = open('tmp/input.txt', 'r')
		sys.stdout = open('tmp/output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


def gcdSum(a, b):
	(a, b) = (min(a, b), max(a, b))
	if a == 0:
		return b
	else:
		return gcdSum(b % a, a)

def s(n):
	return sum([int(x) for x in str(n)])
t = int(input())
for i in range(t):
	n = int(input())
	while True:
		val = gcdSum(n, s(n))
		if val > 1:
			print(n)
			break
		else:
			n += 1


import math
import sys
import operator as op
from functools import reduce
from collections import OrderedDict

class Input:

	@staticmethod
	def string():
		return str(input())

	@staticmethod
	def int():
		return int(input())

	@staticmethod
	def list(sep=' '):
		return input().split(sep)

	@staticmethod
	def list_int(sep=' '):
		return list(map(int, input().split(sep)))

class Output:

	@staticmethod
	def print(res):
		print(res)

	@staticmethod
	def string(res):
		print(str(res))

	@staticmethod
	def list(res):
		print(' '.join((str(x) for x in res)))

class Algorithms:

	@staticmethod
	def isPrime(n):
		return all((n % i != 0 for i in range(2, int(math.sqrt(n) + 1))))

	@staticmethod
	def getPrimeNumbers(n):
		a = [1]
		for num in range(2, n):
			if all((num % i != 0 for i in range(2, int(math.sqrt(num) + 1)))):
				a.append(num)
		return a

	@staticmethod
	def factorization(n):
		res = {}
		for i in range(2, n * n):
			cnt = 0
			while n % i == 0:
				cnt += 1
				n = n / i
			if cnt > 0:
				res[i] = cnt
		if n > 1:
			res[n] = 1
		return res

	@staticmethod
	def gcd(a, b):
		if b == 0:
			return a
		else:
			a = a % b
			return Algorithms.gcd(b, a)

	@staticmethod
	def lcm(a, b):
		return abs(a * b) // Algorithms.gcd(a, b)

	@staticmethod
	def fibonacci(n):
		a = [0, 1]
		for i in range(2, n + 1):
			a.append(a[i - 1] - a[i - 2])
		return a[n]

	@staticmethod
	def z_func(s):
		n = len(s)
		z = [0] * n
		l = r = 0
		for i in range(1, n):
			if r >= i:
				z[i] = min(z[i - l], r - i + 1)
			while z[i] + i < n and s[z[i]] == s[z[i] + i]:
				z[i] += 1
			if i + z[i] - 1 > r:
				l = i
				r = i + z[i] - 1
		return z

def solve():
	n = Input.int()
	n1 = n
	sum = 0
	while n > 0:
		sum = sum + n % 10
		n = n // 10
	while Algorithms.gcd(n1, sum) <= 1:
		n1 += 1
		sum = 0
		n = n1
		while n > 0:
			sum = sum + n % 10
			n = n // 10
	print(n1)
query_count = Input.int()
while query_count:
	query_count -= 1
	solve()


from math import gcd

def fun(n):
	grcd = 0
	while grcd <= 1:
		sm = sum(list(map(int, list(str(n)))))
		grcd = gcd(n, sm)
		n += 1
	print(n - 1)
T = int(input())
for i in range(T):
	st = input()
	fun(int(st))


import math
t = int(input())
solutions = []
while t > 0:
	condition = True
	n = int(input())
	ns = sum([int(x) for x in str(n)])
	while math.gcd(n, ns) <= 1:
		n = n + 1
		ns = sum([int(x) for x in str(n)])
	solutions.append(n)
	t -= 1
for i in solutions:
	print(i)


from sys import stdin, stdout
from math import gcd as g
it = lambda : int(stdin.readline())
st = lambda : stdin.readline().strip()
mp = lambda : map(int, stdin.readline().split())
lt = lambda : list(map(int, stdin.readline().split()))
slt = lambda : stdin.readline().split()
ot = lambda s: stdout.write(str(s) + '\n')
test = it()
for _ in range(test):
	s = st()
	sts = 1
	while sts:
		sums = 0
		for x in s:
			sums += int(x)
		ans = g(int(s), sums)
		if ans > 1:
			ot(s)
			break
		else:
			s = str(int(s) + 1)
			sts += 1


from sys import stdin
from math import gcd
std = stdin.readline
N = int(std())

def plus_num(str1):
	ans = 0
	for s in str1:
		ans += int(s)
	return ans
num = []
for i in range(N):
	n = std().rstrip()
	two = plus_num(n)
	n = int(n)
	num.append((n, two, gcd(n, two)))
for k in num:
	(a, b, c) = k
	if c > 1:
		print(a)
	else:
		while True:
			if c > 1:
				print(a)
				break
			a += 1
			b = plus_num(str(a))
			c = gcd(a, b)


def res(n2, n3):
	MAX = 0
	for i in range(n3, 0, -1):
		if n3 % i == 0 and n2 % i == 0:
			return i
for _ in range(int(input())):
	n = int(input())
	n1 = sum([int(i) for i in str(n)])
	while res(n, n1) == 1:
		n += 1
		n1 = sum([int(i) for i in str(n)])
	print(n)


t = int(input())

def gcd(m, n):
	while n:
		(m, n) = (n, m % n)
	return m
while t:
	n = int(input())
	for x in range(n, n + 100000000):
		c = 0
		s = x
		while s:
			c += s % 10
			s //= 10
		if gcd(x, c) > 1:
			print(x)
			break
	t -= 1


def sum_digits3(n):
	r = 0
	while n:
		(r, n) = (r + n % 10, n // 10)
	return r
t = int(input())
for i in range(0, t):
	num = int(input())
	while num <= 10000000000000000000:
		g = 2
		sum = sum_digits3(num)
		while g <= sum:
			rem1 = num % g
			rem2 = sum % g
			if rem1 == 0 and rem2 == 0:
				print(num)
				num = 10000000000000000001
				break
			else:
				g += 1
		num += 1


import math
tralis = int(input())
answer_list = []

def get_sum(n):
	ans = 0
	for a in str(n):
		ans += int(a)
	return ans
for d in range(tralis):
	m = int(input())
	while True:
		sum_m = get_sum(m)
		if math.gcd(m, sum_m) > 1:
			answer_list.append(m)
			break
		else:
			m += 1
for s in answer_list:
	print(s)


import math
from sys import stdin

def gcdSum(x):
	xSUm = sum(map(int, list(str(x))))
	return math.gcd(x, xSUm)
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	i = n
	while gcdSum(i) == 1:
		i += 1
	print(i)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

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

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[1]

def sort2(l):
	return sorted(l, key=getKey, reverse=True)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

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

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def ceil(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

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

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

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	for _ in range(ii()):
		n = ii()
		while True:
			x = str(n)
			s = 0
			for i in x:
				s += int(i)
			if gcd(s, n) > 1:
				print(n)
				break
			n += 1
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	if a % b == 0:
		return b
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	l = [x for x in str(n)]
	sums = 0
	for i in l:
		sums += int(i)
	ans = gcd(n, sums)
	while ans == 1:
		n += 1
		l = [x for x in str(n)]
		sums = 0
		for i in l:
			sums += int(i)
		ans = gcd(n, sums)
	print(n)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
from math import gcd

def func(x):
	return gcd(x, sum((int(i) for i in str(x))))
(t,) = I()
for _ in range(t):
	(n,) = I()
	for i in range(n, n + 10 ** 5):
		if func(i) > 1:
			print(i)
			break


import sys
import math

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

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

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

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

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	n = II()
	s = 0
	temp = n
	while temp > 0:
		s += temp % 10
		temp //= 10
	while math.gcd(n, s) == 1:
		n += 1
		temp = n
		s = 0
		while temp > 0:
			s += temp % 10
			temp //= 10
	print(n)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	x = int(input())
	g = gcd(x, sum([int(v) for v in str(x)]))
	while g <= 1:
		x = x + 1
		g = gcd(x, sum([int(v) for v in str(x)]))
	print(x)


from math import *
for iii in range(int(input())):
	n = int(input())
	for i in range(n, n + 10):
		a = i
		b = sum([int(c) for c in str(i)])
		if gcd(a, b) > 1:
			print(i)
			break


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, str(n)))
	b = math.gcd(n, sum(a))
	while b <= 1:
		a = list(map(int, str(n)))
		b = math.gcd(n, sum(a))
		if b > 1:
			break
		n = n + 1
	print(n)


from math import floor, ceil
cases = int(input())

def gcd(m, n):
	if n > m:
		return gcd(n, m)
	if m % n == 0:
		return n
	return gcd(n, m % n)

def sum_of_digits(x):
	summ = 0
	strx = str(x)
	for c in strx:
		summ += int(c)
	return summ

def solve():
	n = int(input())
	ns = n
	while gcd(ns, sum_of_digits(ns)) <= 1:
		ns += 1
	print(ns)
for case in range(cases):
	solve()


import math

def Sum(i):
	x = str(i)
	s = 0
	for i in x:
		s += int(i)
	return s
t = int(input())
for i in range(t):
	n = int(input())
	i = n
	while i >= n:
		s = Sum(i)
		gs = math.gcd(i, s)
		if gs > 1:
			print(i)
			break
		i += 1


t = int(input())

def sumOfDigits(n):
	sum_digits = 0
	while n != 0:
		sum_digits += n % 10
		n = n // 10
	return sum_digits

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(t):
	n = int(input())
	while True:
		m = sumOfDigits(n)
		gcdSum = gcd(n, m)
		if gcdSum > 1:
			break
		else:
			n += 1
	print(n)


import math
num = int(input())
while True:
	try:
		a = int(input())
	except EOFError:
		break

	def getsum(n):
		sum = 0
		while n != 0:
			sum = sum + n % 10
			n = n // 10
		return sum
	for i in range(0, num):
		sum_a = getsum(a)
		if math.gcd(a, sum_a) == 1 or sum_a == 1:
			sum_a = sum_a + 1
			a = a + 1
		else:
			a = a
			break
	print(a)


import sys
mod = 998244353
input = lambda : sys.stdin.readline().rstrip('\r\n')
from _collections import deque
from math import ceil, gcd
for counter in range(int(input())):
	n = int(input())
	for j in range(3):
		ck = n + j
		t = 0
		for i in str(ck):
			t += int(i)
		z = gcd(ck, t)
		if z > 1:
			print(ck)
			break


import math
for _ in range(int(input())):
	n = input()
	m = sum(map(int, n))
	o = int(n)
	if o % 10 == 0:
		k = 0
	else:
		k = 1
	for i in range(10 ** 18):
		if k == 1:
			if (o + i) % 10 == 0:
				l = 0
				for j in range(1, 18):
					if (o + i) % 10 ** j == 0:
						continue
					else:
						l = l + j - 1
						break
			else:
				l = 0
		else:
			l = 0
		r = 9 * l * k
		m = m - r
		p = math.gcd(o + i, m + i)
		if p > 1:
			print(o + i)
			break


import math

def digi_sum(n):
	ds = 0
	for i in str(n):
		ds += ord(i) - 48
	return ds
for _ in range(int(input())):
	n = int(input())
	while math.gcd(n, digi_sum(n)) == 1:
		n += 1
	print(n)


import math

def find(n):
	s = 0
	while n != 0:
		s += n % 10
		n //= 10
	return s
for _ in range(int(input())):
	n = int(input())
	for i in range(n, 2 * n + 1):
		if math.gcd(i, find(i)) != 1:
			print(i)
			break


from math import ceil
from math import floor
from math import gcd
from random import random

def ar():
	return [int(x) for x in input().split()]
T = 1
T = int(input())

def solve():
	N = int(input())
	while True:
		L = list(str(N))
		L = [int(x) for x in L]
		if gcd(N, sum(L)) > 1:
			print(N)
			break
		N += 1
for t in range(T):
	solve()


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

def ri():
	return int(input())

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

def sumDigits(n):
	if n < 10:
		return n
	else:
		return n % 10 + sumDigits(n // 10)
t = ri()
for _ in range(t):
	n = ri()
	while True:
		s = sumDigits(n)
		if gcd(n, s) > 1:
			break
		else:
			n += 1
	print(n)


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

def sum_dig(num):
	out = 0
	while True:
		out += num % 10
		num //= 10
		if num == 0:
			break
	return out
num = int(input())
for i in range(num):
	x = int(input())
	while True:
		sum_x = sum_dig(x)
		if gcd(x, sum_x) != 1:
			print(x)
			break
		else:
			x += 1


from sys import stdin, stdout
input = stdin.readline
import math

def gcd(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	while 1:
		n1 = n
		s = 0
		while n1:
			s += n1 % 10
			n1 = n1 // 10
		if gcd(n, s) > 1:
			print(n)
			break
		n += 1


import math
for test in range(int(input())):
	n = input()
	n = int(n)
	while True:
		f = list(map(int, str(n)))
		sm = sum(f)
		if math.gcd(n, sm) > 1:
			print(n)
			break
		else:
			n += 1


from math import gcd

def valid(x):
	return gcd(x, sum([ord(c) - ord('0') for c in str(x)])) != 1
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	while not valid(n):
		n += 1
	print(n)


import sys
import math
input = sys.stdin.readline

def solve():
	n = int(input())
	s = str(n)
	cnt = 5
	while cnt:
		g = math.gcd(n, sum([int(i) for i in s]))
		if g > 1:
			return n
		n += 1
		s = str(n)
		cnt -= 1
	return n
for _ in range(int(input())):
	print(solve())


def sum(n):
	sum = 0
	while n:
		rem = n % 10
		sum = sum + rem
		n = n // 10
	return sum

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

def gcd_number(n):
	return gcd(n, sum(n))
n = int(input())
for i in range(n):
	k = int(input())
	while gcd_number(k) == 1:
		k = k + 1
	print(k)


from math import *

def s(x):
	a = 0
	while x:
		a += x % 10
		x //= 10
	return a
import sys
input = sys.stdin.readline
for i in range(int(input())):
	n = int(input())
	while 1:
		if gcd(n, s(n)) > 1:
			print(n)
			break
		n += 1


t = int(input())

def check(num):
	one = str(num)
	to = 0
	for letter in one:
		to += int(letter)
	return gcd(num, to) > 1

def gcd(num1, num2):
	if num2 == 0:
		return num1
	return gcd(num2, num1 % num2)
for x in range(t):
	n = int(input())
	while not check(n):
		n += 1
	print(n)


import math
for i in [*open(0)][1:]:
	w = int(i)
	q = sum(map(int, list(str(w))))
	while math.gcd(q, w) == 1:
		w += 1
		q = sum(map(int, list(str(w))))
	print(w)


import math

def f(n):
	s = str(n)
	ans = 0
	for i in s:
		ans += int(i)
	return ans

def isPrime(n):
	if n <= 1:
		return False
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	while True:
		if math.gcd(n, f(n)) > 1:
			print(n)
			break
		else:
			n += 1


from math import gcd
from typing import Iterator

def get_num_input() -> Iterator[int]:
	return map(int, input().split())

def main() -> None:
	begin_number: int = int(input())
	while gcd(begin_number, sum(map(int, str(begin_number)))) == 1:
		begin_number += 1
	print(begin_number)
ONLY_ONCE: bool = False
for _ in range(1 if ONLY_ONCE else int(input())):
	main()


from math import gcd

def slv(n):
	while 1:
		sm = sum([int(i) for i in str(n)])
		if gcd(sm, n) > 1:
			print(n)
			return
		n += 1
t = int(input())
for _ in range(t):
	n = int(input())
	slv(n)


import math

def sumofdigits(n):
	a = 0
	while n:
		a += n % 10
		n //= 10
	return a
for _ in range(int(input())):
	n = int(input())
	f = n
	while True:
		if math.gcd(f, sumofdigits(f)) > 1:
			break
		f += 1
	print(f)


def computeGCD(x, y):
	if x > y:
		small = y
	else:
		small = x
	for i in range(1, small + 1):
		if x % i == 0 and y % i == 0:
			gcd = i
	return gcd

def sumofdigits(n):
	sum = 0
	for digit in str(n):
		sum += int(digit)
	return sum

def result(num):
	answer = computeGCD(num, sumofdigits(num))
	if answer > 1:
		print(num)
	else:
		num += 1
		result(num)
for tc in range(int(input())):
	number = int(input())
	result(number)


n = int(input())

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

def sum_digit(n):
	res = 0
	while n:
		res += n % 10
		n //= 10
	return res
for _ in range(n):
	num = int(input())
	while gcd(num, sum_digit(num)) == 1:
		num += 1
	print(num)


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

def sum(n):
	res = 0
	while n > 0:
		res = res + n % 10
		n = n // 10
	return res

def gcdSum(n):
	s = sum(n)
	gcdSum = gcd(n, s)
	return gcdSum

def find(n):
	if gcdSum(n) > 1:
		return n
	if gcdSum(n + 1) > 1:
		return n + 1
	if gcdSum(n + 2) > 1:
		return n + 2
t = int(input())
for i in range(t):
	n = int(input())
	print(find(n))


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

def gcdSum(n):
	j = n
	b = False
	k = n
	while True:
		digit_sum = 0
		j = k
		while j > 0:
			digit_sum += j % 10
			j = j // 10
		if gcd(k, digit_sum) != 1:
			return k
		else:
			k += 1
n = int(input())
i = n
ans = list()
while i > 0:
	num = int(input())
	ans.append(gcdSum(num))
	i -= 1
for i in range(len(ans)):
	print(ans[i])


import math

def sumOfDigi(num):
	return sum([int(i) for i in str(num)])
n = int(input())
for _ in range(n):
	num = int(input())
	digitsSum = sumOfDigi(num)
	while math.gcd(num, digitsSum) <= 1:
		num += 1
		digitsSum = sumOfDigi(num)
	print(num)


from math import gcd
T = int(input())
for t in range(T):
	n = int(input())
	strn = str(n)
	S = sum([int(x) for x in strn])
	while gcd(n, S) <= 1:
		n += 1
		strn = str(n)
		S = sum([int(x) for x in strn])
	print(n)


from collections import defaultdict
import math

def fun(n):
	ans = 0
	for j in n:
		ans += int(j)
	return math.gcd(int(n), ans) - 1
t = int(input())
res = []
for _ in range(t):
	n = int(input())
	ans = n
	while not fun(str(ans)):
		ans += 1
	print(ans)


import sys
from fractions import Fraction
from collections import Counter

def f1(a):
	s = 0
	while a != 0:
		s = s + a % 10
		a = a // 10
	return s

def f(a):
	flag = 0
	while flag == 0:
		if compute_gcd(a) == 1:
			a = a + 1
			continue
		flag = 1
	return a

def compute_gcd(x):
	y = f1(x)
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
input = sys.stdin.read()
data = list(map(int, input.split()))
t = data[0]
l = 0
for i in range(t):
	n = data[l + 1]
	print(f(n))
	l = l + 1


from math import gcd

def sumOfDigits(x):
	x = str(x)
	ans = 0
	for i in x:
		ans += int(i)
	return ans
for _ in range(int(input())):
	n = int(input())
	ans = 0
	while gcd(n, sumOfDigits(n)) == 1:
		n += 1
	print(n)


def gcd(a, b):
	while a > 0 and b > 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return max(a, b)
t = int(input())
for i in range(t):
	n = int(input())
	while True:
		if n % 3 == 0:
			print(n)
			break
		if gcd(n, sum(map(int, str(n)))) > 1:
			print(n)
			break
		n += 1


import sys
from math import gcd
input = lambda : sys.stdin.readline().rstrip()

def get_dig_sum(x):
	return sum([ord(d) - ord('0') for d in str(x)])

class Problem:

	def __init__(self):
		pass

	def solve(self):
		n = int(input())
		x = n
		while True:
			y = get_dig_sum(x)
			z = gcd(x, y)
			if z > 1:
				break
			x += 1
		print(x)

def main():
	p = Problem()
	t = int(input())
	while t:
		p.solve()
		t -= 1
main()


import math

def gcdsum(x):
	y = [int(d) for d in str(x)]
	a = 0
	for i in range(len(y)):
		a += y[i]
	return math.gcd(x, a)
t = int(input())
for z in range(t):
	x = int(input())
	while gcdsum(x) <= 1:
		x += 1
	print(x)


import sys
import math

def sumofn(n):
	summ = 0
	while n > 0:
		summ += n % 10
		n //= 10
	return summ

def gcdSum(n):
	n2 = sumofn(n)
	ans = math.gcd(n, n2)
	return ans

def answer(n):
	while gcdSum(n) == 1:
		n += 1
	return n

def main():
	t = int(input())
	while t:
		n = int(input())
		print(answer(n))
		t -= 1
	return
main()


from sys import stdin
from math import gcd

def gc(x):
	x1 = 0
	for i in str(x):
		x1 += int(i)
	return gcd(x, x1)
n = int(stdin.readline().strip())
inf = 10 ** 20
for i in range(n):
	x = int(stdin.readline().strip())
	for j in range(x, inf):
		if gc(j) > 1:
			print(j)
			break


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
t = int(input())

def GCD(a, b):
	if not b:
		return a
	return GCD(b, a % b)

def gcdSum(x):
	return GCD(x, sum([int(i) for i in str(x)]))
for _ in range(t):
	n = int(input())
	while gcdSum(n) == 1:
		n += 1
	print(n)


import sys
input = sys.stdin.readline
import math

def inpit():
	return int(input())

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

def inpstr():
	s = input()
	return list(s[:len(s) - 1])

def inpspit():
	return map(int, input().split())
import math

def lcm(a):
	return abs(math.prod(a)) // math.gcd(*a)
t = inpit()
for i in range(t):
	n = inpit()
	f = True
	while f == True:
		lt = [int(j) for j in str(n)]
		s = math.gcd(n, sum(lt))
		if s > 1:
			print(n)
			f = False
			break
		else:
			n = n + 1