Link SPOJ: https://www.spoj.com/problems/PALIN/

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.

### Input

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

### Ouput

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

### Restriction

Time limit: | 2s-9s |

Source limit: | 50000B |

Memory limit: | 1536MB |

### Example

```
Input:
2
808
2133
Output:
818
2222
```

Please try to solve first, before moving into the solution.

**Solution: **

**AC Code: **