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$

输入格式

输入的第一行为一个整数$t$$（1\le t\le 10^4）$——测试用例的数量。 接下来是$t$行，每行包含一个整数$n$ $(1 \le n \le 10^{18})$ 。 一个测试中的所有测试用例都是不同的。

输出格式

输出$t$行，其中第$i$行是一个包含第$i$th测试用例答案的单个整数。

样例 #1

样例输入 #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$的最小数字$\ge11$是$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$的最小数字$\ge31$是$33$。 测试用例3:$n=75$： $\text｛$gcdSum$｝（75）=gcd（75，7+5）=gcd（75，12）=3$。 $75$的$\text｛$gcdSum$｝$已经是$>1$。因此，这就是答案。