Mouse Stofl is currently on holidays in the mysterious country of Bitland, where the wise Mouse Brodowskl rules over his empire. Brodowskl has heard of Mouse Stofl's talent to solve problems, but since Mouse Stofl is on holidays and doesn't want to do any work, Stofl needs your help to complete the following task.

In Bitland, palaces are described by a sequence of numbers, such as 23145; the individual digits describe the height of the palace at various positions, if the palace is viewed from the front. On the one hand, mouse Brodowskl loves palaces, but even more so, he loves palaces that are symmetric in appearance, such as the palace described by the number 37973. On the other hand, he also loves to throw parties for all of his people. It is customary in Bitland, to throw a party whenever the (growing) population of Bitland reaches the number corresponding to a palace. Brodowskl is thinking about building another symmetric palace, but he first wants to know by how many people the population has to grow until it matches the palace's number, if the palace is chosen such that this number is minimized.

We say a number is symmetric, if its sequence of digits is the same when reading them from left to right as when reading from right to left. So $121$, $44544$, $7337$ are all symmetric, but $233$, $9595$ and $800$ are not symmetric. Note that you should not have leading zeros, so $00800$ is not a symmetric number.

Given the population of Bitland $N$, find the smallest integer $K$, such that $N+K$ is symmetric.

A single integer $N$, with $0 < N < 2^{63}$

A single integer $K$, such that $N+K$ is a symmetric number.

For 50% of the points it holds that $0 < N < 2^{31}$.

Input | Output | |

123 141 3541 129999931 |
8 0 12 100 |

Input-Files | Output-Files |

sample.in | sample.out |

sample_medium.in | sample_medium.out |

sample_large.in | sample_large.out |

If you have any questions, feel free to ask in the forum or send us an email at info[at]soi[dot]ch.