While driving the other day, Franck looked down at his odometer, and it read “100000” kilometres. He was pretty excited about that. But, just one kilometre further, the odometer read “100001”, and he was really excited! You see, Franck loves palindromes, things that read the same way forwards and backwards.
So, given any odometer reading, what is the least number of kilometres that Franck must drive further before the odometer reading is a palindrome? For Franck, every odometer digit counts. E.g., if the odometer reading was “000121”, he would not consider that a palindrome (and be excited about it).
There will be a time limit on your program's execution. The naïve approach, for instance, of just adding one iteratively and checking each time if it is a palindrome yet will time out.
There will be several test cases in the input. Each test case will consist of an odometer reading on its own line. Each odometer reading will be from 2 to 20 digits long. The odometer in question has the number of digits as given in the input. E.g., if the input is “00456”, the odometer has 5 digits. There will be no spaces in the input, and no blank lines between input sets. The input will end with a line with a single “0”.
100000 100001 000121 00456 31415926535897932384 0
For each test case, output the minimum number of kilometres Franck must drive before the odometer reading is a palindrome. This may be “0”, if the number is already a palindrome. Output each integer on its own line, with no extra spaces and no blank lines between outputs.
1 0 979 44 8665019029