Reyno's family has an unusual tradition: upon buying your bus ticket, you check if it's
lucky (and if it is, you eat it, but that's beside the point). Each ticket has a serial number
containing an even number of digits, and a ticket is considered lucky if the sum of the
digits in the first half of the number equals the sum of digits of the second half.
For example, `113311`

and `113005`

are both lucky, but `113331`

is not; the next ticket
after `113331`

that is lucky is `113401`

.
Given the serial number of a ticket, find the serial number of the next lucky ticket.

#### Input Specification

The first line on input contains , the number of test cases. test cases follow. Each test case contains an integer , the serial number of a ticket. will have an even number of digits and may be given with leading zeroes.

#### Output Specification

For each test case, your program should output one integer, the next lucky ticket.

#### Sample Input

```
3
113005
113331
123456789123455789
```

#### Sample Output

```
113014
113401
123456789123455799
```

## Comments