N. Larger but smaller!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer $$$x$$$. Find the smallest integer $$$y$$$ that satisfy the following:

  • $$$y \gt x$$$
  • $$$string(y) \lt string(x)$$$

Here, $$$string(x)$$$ is the decimal representation of $$$x$$$ (without leading zeros) as a string.

Strings are compared lexicographically$$$^\dagger$$$. For example,

  • $$$string(1111) \lt string(123)$$$;
  • $$$string(123456789) \lt string(9)$$$;
  • $$$string(33) \lt string(333)$$$.

If such an integer $$$y$$$ does not exist, print $$$-1$$$.

$$$^\dagger$$$ A string $$$s$$$ is lexicographically larger than a string $$$t$$$ if and only if one of the following holds:

  • $$$t$$$ is a prefix of $$$s$$$, but $$$s \neq t$$$;
  • in the first position where $$$s$$$ and $$$t$$$ differ, the string $$$s$$$ has a larger character (digit) than the corresponding character (digit) in $$$t$$$.
Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ — the number of test cases. The description of the test cases follows.

The first and only line of each test case contains a single integer $$$x$$$ $$$(1 \le x \le 10^{18})$$$.

Output

For each test case:

  • If there is no such integer $$$y$$$, output a single line containing $$$-1$$$.
  • Otherwise, output a single line containing $$$y$$$.
Example
Input
1
9
Output
10