CF1498A.GCD Sum

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) \gt 1.

一个正整数的 \text{gcdSum} 定义为该整数与其各位数字之和的最大公约数。形式化地，对正整数 $x$，有 \text{gcdSum}(x) = \gcd(x, \text{ } x \text{ 的各位数字之和})。其中 $\gcd(a, b)$ 表示 $a$ 与 $b$ 的最大公约数——即能同时整除 $a$ 和 $b$ 的最大整数 $d$。

例如：\text{gcdSum}(762) = \gcd(762,\ 7 + 6 + 2) = \gcd(762,\ 15) = 3。

给定一个整数 $n$，请找出满足 \text{gcdSum}(x) > 1 的最小整数 $x \ge n$。

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.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来是 $t$ 行，每行包含一个整数 $n$（$1 \le n \le 10^{18}$）。

同一组测试中的所有测试用例互不相同。

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

输出 $t$ 行，其中第 $i$ 行是一个整数，表示第 $i$ 个测试用例的答案。

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$ $ \gt 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$ $ \gt 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 $ \gt 1$. Hence, it is the answer.

我们来解释样例中的三个测试用例。

测试用例 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。

因此，大于等于 $11$ 且其 \text{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。

因此，大于等于 $31$ 且其 \text{gcdSum} > 1 的最小数是 $33$。

测试用例 3：$n = 75$：

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

$75$ 的 \text{gcdSum} 已经大于 $1$，因此答案就是 $75$。