Palindrometer


Description

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).


Hint

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.


Input

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”.


Sample Input

100000
100001
000121
00456
31415926535897932384
0

Output

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.


Sample Output

1
0
979
44
8665019029