91 - ZOJ Monthly, May 2010 - F
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.)
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).
For each test case, if you can find the integer y, output the result in a single line, otherwise output "Impossible"(without quotes) instead.
4 5435324 919 11 1
5440445 14941 101 Impossible
Note: No input data start with digit 0 and you should not output a number starts with 0.