Palindromic Password

Interview

Time limit3sMemory limit512 MB

Summary

For each six-digit number, print the closest six-digit palindrome, breaking ties by choosing the smaller one.

Level: Easy3 of 10
Topics: Array, Brute force, Math
Solved: No attempts yet

Problem

The IT department at your school changed its password rules. A password is $N$ six-digit numbers joined by hyphens, and $N$ depends on the phase of the moon and the next day's weather forecast.

If every one of those six-digit numbers is a palindrome (it reads the same forwards and backwards), you only have to remember $N$ three-digit numbers. So you take a list of $N$ randomly generated six-digit numbers and replace each one with the six-digit palindrome closest to it.

Write a program that performs this replacement for you.

Input

The first line contains the count $N$ of six-digit numbers. ( $1 \le N \le 1000$ )

Each of the next $N$ lines contains one six-digit number. The number has no leading zero, so it is between $100000$ and $999999$ .

Output

For each number given in the input, print on its own line the six-digit palindrome closest to it. Closest means the absolute difference with the original number is the smallest. If two palindromes tie for the smallest difference, print the smaller one. The printed number must not have a leading zero either.

Examples7

Example 1
Input
```
2
123321
123322
```
Expected output
```
123321
123321
```
Example 2
Input
```
1
100000
```
Expected output
```
100001
```
Example 3
Input
```
1
999999
```
Expected output
```
999999
```

Example 4

Input

Expected output

Example 5

Input

Expected output

Example 6

Input

Expected output

Example 7

Input

Expected output