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.
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.
Print out in each line the largest prime number found in each input string.