正整数的 $$$\text{$$$gcdSum$$$}$$$ 是该整数的 $$$gcd$$$ 及其数字之和。形式上,对于正整数 $$$x$$$,$$$\text{$$$gcdSum$$$}(x) = gcd(x, \text{ x 的数字之和)$$$。 $$$gcd(a, b)$$$ 表示 $$$a$$$ 和 $$$b$$$ 的最大公约数 — 使得整数 $$$a$$$ 和 $$$b$$$ 都能被 $$$d$$$ 整除的最大整数 $$$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$$$ 测试用例的答案。
示例
输入 #1
3 11 31 75
输出 #1
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$$$。
因此,$$$gcdSum$$$ $$$> 1$$$ 的最小数字 $$$\ge 11$$$ 是 $$$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$$$。
因此,$$$gcdSum$$$ $$$> 1$$$ 的最小数字 $$$\ge 31$$$ 是 $$$33$$$。
测试用例 3:$$$\ n = 75$$$:
$$$\text{$$$gcdSum$$$}(75) = gcd(75, 7 + 5) = gcd(75,\ 12) = 3$$$。
$$$75$$$ 的 $$$\text{$$$gcdSum$$$}$$$ 已经是 $$$> 1$$$。因此,这就是答案。