The palindrome (pronounced "ballin' drone") is a phrase or number that can be read the same way forwards or backwards. The palindrome was first discovered by Sarah Palin, who named the palindrome after herself after a night of observing the natives of Russia, a largely unexplored Asian landmass across the Pacific Ocean, from her Alaskan cottage. It is theorized and accepted by many members of the scientific community that all numbers in Russia are palindromes.
The reason for Russia's dependence on the palindrome is quite clear. During the 18th century, palindromes were primarily imported into Russia from Turkey, whose fertile soils and warm South American weather made it apt for growing it. However, in May of 1770, during the height of the Russo-Turkish War, Catherine the Great decreed a ban on importing palindromes to make Russia independent from the exports of its enemy, further modernizing the country by forcing Russians to create their own. As a result, non-palindromic numbers were forsaken in the Russian Empire, in order to conserve the necessary numbers and characters to create enough palindromes for the entire Russian populace. The day after Catherine's decree, the year was forcibly changed to 1771.
Today, a large portion of Russia's economy is still driven on the creation of palindromes, where it has become tradition to train young Russian children in palindrome cultivation. Google cofounder Sergey Brin grew and bottled his own premium palindromes as a child in the suburbs of Moscow. His aged palindromes have become a collector's item, and are valued at upwards of $5M USD.
Leo was fortunate enough to be able to experience one of Brin's palindromes first hand. For Project Feng, he's decided to educate all of its participants on the arcane art of Russian palindrome cultivation. Given a positive integer ~N~, find the smallest integer authentic Russian palindrome that is larger than ~N~.
The first and only line will contain the positive integer ~N~. ~N~ will have at most ~10^6~ digits, another property that all numbers in Russia meet (but that's a story for another time). For 20% of all possible points, ~N~ will have less than ~5~ digits.
There is large input data in this problem.
On a single line, output the smallest palindrome greater than ~N~.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2