# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.# Problem

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

The first line on input contains T (1 \leq T \leq 100), the number of test cases. T test cases follow. Each test case contains an integer N, (1 \leq N \leq 10^{100}), the serial number of a ticket. N will have an even number of digits and may be given with leading zeroes, however N will never have every single digit be nine.

# Output

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