Problem 1: Prime Palindromes, (K Narayan Kumar, CMI)
An integer is said to be a palindrome if it is equal to its reverse. For example, 79197 and 324423 are palindromes. In this task you will be given an integer N, 1 ≤ N ≤ 1000000. You must find the smallest integer M ≥ N such that M is a prime number and M is a palindrome.
For example, if N is 31 then the answer is 101.
Input format
A single integer N, (1 ≤ N ≤ 1000000), on a single line.
Output format
Your output must consist of a single integer, the smallest prime palindrome greater than or equal to N.
Example
We now illustrate the input and output formats using the example described above.
Sample input:
31
Sample output:
101
Test data: