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
A single integer N, (1 ≤ N ≤ 1000000), on a single line.

Output
Your output must consist of a single integer, the smallest prime
palindrome greater than or equal to N.

Example

Input:
31
Output:
101
#!/usr/bin/env python
import sys

primes = [2]

def isPrime(N):
    sqrtN = N ** 0.5
    for d in primes:
        if d > sqrtN:
            return True
        if N % d == 0:
            return False
    return True

def fillPrimes(maxVal):
    for i in xrange(primes[-1] + 1, maxVal, 2):
        prime = True
        if isPrime(i):
            primes.append(i)

def findPrPalin(N):
    if N % 2 == 0:
        N += 1

    while True:
        if isPrime(N):
            primes.append(N)
            strN = str(N)
            if strN == strN[::-1]:
                return N
        N += 2

if __name__ == '__main__':
    N = int(sys.stdin.readline().strip())
    if N in [1, 2]:
        print N
    else:
        fillPrimes(N)
        print findPrPalin(N)