Indian National Olympiad in Informatics

Online Programming Contest, 4-5 September 2004


Basic Division

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.


We now illustrate the input and output formats using the example described above.

Sample input:


Sample output:


Test data:

Copyright (c) IARCS 2003-2020;   Last Updated: 21 September 2004