시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 409 165 146 45.062%

문제

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

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

입력

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

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

출력

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

예제 입력 1

11245
91321150448
1226406
0

예제 출력 1

11
1321
2

힌트

W3sicHJvYmxlbV9pZCI6IjU2MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzE4Y1x1YzIxOFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCAyXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxOGNcdWMyMThcdWI5Y2MgXHVjMThjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxLDAwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgMjU1XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMjJiXHVjNzkwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzE4Y1x1YzIxOCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHJpbWUgU3Vic3RyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHN0cmluZyBvZiBkaWdpdHMsIHlvdXIgdGFzayBpcyB0byBmaW5kIHRoZSBsYXJnZXN0IHByaW1lIG51bWJlciB3aGljaCBwcmVzZW50cyBpbiB0aGF0IHN0cmluZy4gT3VyIHByaW1lIG51bWJlcnMgYXJlIHZhbHVlcyBiZXR3ZWVuIDIgdG8gMTAwLDAwMCBvbmx5LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBsaW5lIGNvbnRhaW5zIGEgc3RyaW5nIG9mIGRpZ2l0cyAoMjU1IGRpZ2l0cyBhdCBtb3N0KS4gVGhlIGxpbmUgY29udGFpbnMgb25seSAwIGluZGljYXRlcyB0aGUgZW5kIHdoaWNoIHdpbGwgbm90IGJlIHByb2Nlc3NlZC4gVGhlIGlucHV0IGRvZXMgbm90IGV4Y2VlZCAxLDAwMCBsaW5lcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBvdXQgaW4gZWFjaCBsaW5lIHRoZSBsYXJnZXN0IHByaW1lIG51bWJlciBmb3VuZCBpbiBlYWNoIGlucHV0IHN0cmluZy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=