← 返回题目列表

Codeforces · 1498/A

A. GCD 总和

中文机器翻译题面 查看原题

正整数的 $$$\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$$$。因此,这就是答案。