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