Prime Palindrome

Interview

Time limit2sMemory limit256 MB

Summary

Find the smallest number greater than or equal to N that is both a prime and a palindrome.

Level: Easy3 of 10
Topics: Math, Brute force, Implementation
Solved: No attempts yet

Problem

An integer is called a palindrome number if it reads the same from left to right and from right to left. For example, 79,197 and 324,423 are palindrome numbers.

Given an integer N (1 ≤ N ≤ 1,000,000), write a program that finds the smallest integer greater than or equal to N that is both prime and a palindrome number.

Input

The first line contains N.

Output

Print the number that satisfies the conditions.

Examples1

Example 1
Input
```
31
```
Expected output
```
101
```