CSES - Datatähti Open 2021 - Greater Integers
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Find the smallest integer greater than nn where each digit is the same.

Input

The first line of input consists of an integer tt: the number of test cases.

The following lines each represent one test case, containing the integer nn.

Output

Print the answer for each test on separate lines.

Example

Input:

3
5
9
123

Output:

6
11
222

Subtask 1 (35 points)

  • 1t10001 \le t \le 1000
  • 1n10001 \le n \le 1000

Subtask 2 (65 points)

  • 1t10001 \le t \le 1000
  • 1n10181 \le n \le 10^{18}