Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3339
Palindrom

Time Limit: 1 Second      Memory Limit: 32768 KB

We say that a number is a palindrom if it is the same when read from left to right or from right to left. For example, both the numbers 1221 and 75457 are palindroms. Here comes the problem: Given a positive integer x, find the smallest palindrom y which is greater than x and has the same digit sum as x. (That is the sum of all y's digits is equal to the sum of all x's digits.)

Input

There are multiple test cases. The first line of input is an integer T (0<T<=500) indicating the number of test cases. Then T test cases follow. Each case is an integer x (0<x<=1010000).

Output

For each test case, if you can find the integer y, output the result in a single line, otherwise output "Impossible"(without quotes) instead.

Sample Input

```4
5435324
919
11
1
```

Sample Output

```5440445
14941
101
Impossible
```

Note: No input data start with digit 0 and you should not output a number starts with 0.

Author: CAO, Peng
Source: ZOJ Monthly, May 2010
Submit    Status