소수 부분 문자열

시간 제한1초메모리 제한128 MB

요약

숫자로 이루어진 문자열이 주어질 때, 100000 이하의 소수 가운데 가장 큰 값을 갖는 연속 부분 문자열을 찾는다.

문제

숫자로만 이루어진 문자열이 주어진다. 이 문자열의 연속된 부분 문자열을 정수로 해석했을 때, 소수가 되는 것 중에서 값이 가장 큰 것을 찾는 프로그램을 작성하시오.

이 문제에서는 $2$ 이상 $100{,}000$ 이하인 소수만 소수로 본다.

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

각 테스트 케이스는 한 줄에 주어지며, 길이가 $255$ 를 넘지 않는 숫자 문자열이다. 입력의 마지막 줄에는 $0$ 하나만 주어지며, 이는 입력의 끝을 의미한다.

소수인 부분 문자열이 적어도 하나 존재하는 입력만 주어진다.

각 테스트 케이스마다, 소수인 부분 문자열 중 값이 가장 큰 것을 한 줄에 하나씩 출력한다.