A. GCD Sum
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$\text{$$$gcdSum$$$}$$$ положительного целого числа — это $$$gcd$$$ этого числа и суммы его цифр. Формально, $$$\text{$$$gcdSum$$$}(x) = gcd(x, \text{ сумма цифр } x)$$$ для положительного целого $$$x$$$. $$$gcd(a, b)$$$ обозначает наибольший общий делитель $$$a$$$ и $$$b$$$ — наибольшее целое число $$$d$$$, такое, что оба числа $$$a$$$ и $$$b$$$ делятся на $$$d$$$.

Например: $$$\text{$$$gcdSum$$$}(762) = gcd(762, 7 + 6 + 2)=gcd(762,15) = 3$$$.

Вам дано целое число $$$n$$$. Найдите наименьшее целое число $$$x \ge n$$$, для которого $$$\text{$$$gcdSum$$$}(x) > 1$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных.

Затем следуют $$$t$$$ строк, каждая из которых содержит одно целое число $$$n$$$ $$$(1 \le n \le 10^{18})$$$.

Все наборы входных данных в одном тесте различны.

Выходные данные

Выведите $$$t$$$ строк, $$$i$$$-я из которых должна содержать одно целое число — ответ на $$$i$$$-й набор входных данных.

Пример
Входные данные
3
11
31
75
Выходные данные
12
33
75
Примечание

Объяснение трех наборов входных данных из примера:

Набор 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$$$.

Значит, минимальное целое число $$$\ge 11$$$, для которого $$$gcdSum$$$ $$$> 1$$$ — это $$$12$$$.

Набор 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$$$.

Значит, минимальное целое число $$$\ge 31$$$, для которого $$$gcdSum$$$ $$$> 1$$$ — это $$$33$$$.

Набор 3: $$$\ n = 75$$$:

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

$$$\text{$$$gcdSum$$$}$$$ числа $$$75$$$ уже $$$> 1$$$. Значит, это число и является ответом.