시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 392 149 131 43.377%

문제

숫자로 이루어진 문자열이 주어진다. 이 때, 부분 문자열 중에서 가장 큰 소수를 찾는 프로그램을 작성하시오.

이 문제에서는 2보다 크거나 같고, 100,000보다 작거나 같은 소수만 소수이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 1,000개를 넘지 않는다.

각 테스트 케이스는 길이가 255를 넘지 않는 숫자 문자열로 이루어져 있다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 가장 큰 소수 부분 문자열을 출력한다. 

예제 입력

11245
91321150448
1226406
0

예제 출력

11
1321
2

힌트