Looping Prime

题号：NC217548
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

A digit string is a string consisting only of digits from '0' to '9' (both inclusive). Let $s = s_1s_2\cdots s_n$ be a digit string, define the following functions:

$\begin{cases}r(s) = s_ns_1s_2\cdots s_{n-1} \\ R^0(s) = s \\ R^k(s) = r(R^{k-1}(s))\end{cases}$

We say a digit string is a prime string if after parsing it to an integer, this integer is a prime. A digit string $s = s_1s_2\cdots s_n$ is called a looping prime string if for all $0 \le k < n$ , $R^k(s)$ is a prime string.

Given a digit string $s$ , please find a substring of $s$ such that the substring is a looping prime string and after parsing it to an integer the result is as large as possible.

Note that when parsing a digit string to an integer, its leading zeros will be discarded. For example, string "000123" will be parsed to integer 123. But this does not influence the string itself. For example, $r(\text{‘000123'}) = \text{‘300012'}$ , not "312".

输入描述:

There is only one test case in a single test file.

The first and only line contains a digit string $s$ ( $1 \le |s| \le 10^5$ ), $|s|$ means the length of string $s$ .

Please note that, although the length of $s$ is selected by hand, the content of $s$ is randomly generated. Each digit has equal probability to appear in each position of the string.

输出描述:

    Output one line containing one string, indicating the answer. If the answer does not exist, output "-1" (without quotes) instead.

示例1

输入

复制

输出

复制

说明

As "971", "197" and "719" are prime strings, "971" is a looping prime string. While "2971" is a prime string,  is obviously not. So the answer is 971.

示例2

输入

复制

输出

复制

-1

说明

The sample test case is (obviously) constructed by hand to illustrate the case when an answer does not exist. The contents of the digit strings in the real test cases will be randomly generated.