Problems

# Prime Substring

# Prime Substring

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 100000 only.

## Input data

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 1000 lines.

## Output data

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

## Examples

Input example #1

11245 91321150448 1226406 0

Output example #1

11 1321 2