CF1498A GCD Sum

一个正整数的 $ \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 翻译