GCD Sum

The \text{gcdSum} of a positive integer is the gcd of that integer with its sum of digits. Formally, \text{gcdSum}(x) = gcd(x, 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 ≥ n such that \text{gcdSum}(x) > 1.

Input

The first line of input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Then t lines follow, each containing a single integer n (1 ≤ n ≤ 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 ≥ 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 ≥ 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.

inputFormat

Input

The first line of input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Then t lines follow, each containing a single integer n (1 ≤ n ≤ 10^{18}).

All test cases in one test are different.

outputFormat

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

样例

3
11
31
75

12
33
75

</p>