GCD Sum

题意翻译

$\operatorname{gcdSum(x)=}\gcd(x,\sum_{i=1}^ka_i)$ 其中 $a_i$ 表示 $x$ 的从左到右第 $i$ 位，$k$ 表示 $x$ 的位数。 例如 $\operatorname{gcdSum(762)}=\gcd(762,2+6+7)=\gcd(762,15)=3$ 给定一个 $n$，请你找到一个最小的整数 $x$ 满足： - $x\ge n$ - $\operatorname{gcdSum(x)}>1$

题目描述

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 $ .

输入输出格式

输入格式

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 $ t $ lines, where the $ i $ -th line is a single integer containing the answer to the $ i $ -th test case.

输入输出样例

输入样例 #1

3
11
31
75

输出样例 #1

12
33
75

说明

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.