SP5 PALIN - The Next Palindrome

A positive integer is called a **palindrome** if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer $K$ of not more than $1000000$ digits, write the value of the smallest palindrome larger than $K$ to output. Numbers are always displayed without leading zeros.

The first line contains integer $t$, the number of test cases. Integers $K$ are given in the next $t$ lines.

For each $K$, output the smallest palindrome larger than $K$.

For $100\%$ of the data, $|K| \le 1000000$, where $|K|$ denotes the number of digits of $K$. **Warning: large Input/Output data, be careful with certain languages**