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.


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.


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.


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

Sample Input


Sample Output