J. palprime
time limit per test
4 seconds
memory limit per test
24 megabytes
input
standard input
output
standard output

A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number. Palindromicity depends on the base of the numbering system and its writing conventions, while primality is independent of such concerns.

The sequence of binary palindromic primes begins(in binary):

11, 101, 111, 10001, 11111, 1001001 You are given a number b (in binary), you should output the first palprime greater than or equal to b.

Input

The input consists of multiple test cases, each test case consists of a number b in binary.

We guarantee b will be no Longer than 21 bits

Output

The first palprime greater than or equal to b

Examples
Input
10
100
110
1000
Output
11
101
111
10001