题目描述

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

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

给定一个整数 $n$，请你找到最小的整数 $x \geq n$，使得 $\text{gcdSum}(x) > 1$。

输入格式

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

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

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

输出格式

输出 $t$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案，即满足条件的最小整数。

说明/提示

下面解释样例中的三个测试用例。

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

所以，最小的 $\geq 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$。

所以，最小的 $\geq 31$ 且 $\text{gcdSum} > 1$ 的数是 $33$。

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

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

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

由 ChatGPT 4.1 翻译

样例

3
11
31
75

12
33
75