Prime Palindromes

You are given a series of positive integers, one per line. For each integer, you need to find the smallest Prime Palindrome that is greater than or equal to the given number. A number is a Prime Palindrome if it is both a prime number and a palindrome. The input terminates with a 0, which should not be processed.

Recall that a prime number is a number greater than 1 that has no divisors other than 1 and itself, and a palindrome is a number that reads the same backward as forward. The answer for each test case should be printed on its own line.

inputFormat

The input will be given via standard input. Each line contains a single integer n (1 ≤ n ≤ 10⁸). The input ends when a line containing 0 is encountered. You should process all numbers before the terminating zero.

outputFormat

For each integer in the input (except the terminating 0), output the smallest prime palindrome greater than or equal to that integer on a separate line via standard output.

31
45
90
0

101
101
101