Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. GCD Sum

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe $$$\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$$$.

Input

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

Output $$$t$$$ lines, where the $$$i$$$-th line is a single integer containing the answer to the $$$i$$$-th test case.

Example

Input

3 11 31 75

Output

12 33 75

Note

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2021 18:52:30 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|