Largest Prime Substring

Time limit1sMemory limit128 MB

Summary

Given a digit string, find the largest-valued contiguous substring that is prime and at most 100000.

Level: Medium5 of 10
Topics: String, Brute force, Number theory, Prefix sum
Solved: No attempts yet

Problem

You are given a string consisting only of digits. Write a program that, among all contiguous substrings of the string interpreted as integers, finds the one that is prime and has the largest value.

In this problem, a number is considered prime only if it is a prime between $2$ and $100{,}000$ inclusive.

Input

The input consists of several test cases. The number of test cases does not exceed $1{,}000$ .

Each test case is given on its own line as a digit string whose length does not exceed $255$ . The last line of the input contains a single $0$ , which marks the end of the input.

Only inputs in which at least one substring is prime are given.

Output

For each test case, print on its own line the largest-valued prime substring.

Examples3

Example 1
Input
```
11245
91321150448
1226406
0
```
Expected output
```
11
1321
2
```
Example 2
Input
```
2
0
```
Expected output
```
2
```
Example 3
Input
```
99991
0
```
Expected output
```
99991
```