Prime Substring

Time Limit: 10000ms

Memory Limit: 65535kb

Description

Given a string of digits, your task is to find the largest prime number which presents in that string. Our prime numbers are values between 2 to 100,000 only.

Input

Each line contains a string of digits (255 digits at most). The line contains only 0 indicates the end which will not be processed. The input does not exceed 1,000 lines.

Output

Print out in each line the largest prime number found in each input string.

Sample Input

11245
91321150448
1226406
0

Sample Output

11
1321
2

Hint

None

Source

None

提交代码