시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 442 180 158 44.886%

문제

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

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

입력

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

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

출력

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

예제 입력 1

11245
91321150448
1226406
0

예제 출력 1

11
1321
2
W3sicHJvYmxlbV9pZCI6IjU2MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMThjXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IDJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YjljYyBcdWMxOGNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDEsMDAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCAyNTVcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWMyMmJcdWM3OTAgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU2MzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmltZSBTdWJzdHJpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgc3RyaW5nIG9mIGRpZ2l0cywgeW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIGxhcmdlc3QgcHJpbWUgbnVtYmVyIHdoaWNoIHByZXNlbnRzIGluIHRoYXQgc3RyaW5nLiBPdXIgcHJpbWUgbnVtYmVycyBhcmUgdmFsdWVzIGJldHdlZW4gMiB0byAxMDAsMDAwIG9ubHkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGxpbmUgY29udGFpbnMgYSBzdHJpbmcgb2YgZGlnaXRzICgyNTUgZGlnaXRzIGF0IG1vc3QpLiBUaGUgbGluZSBjb250YWlucyBvbmx5IDAgaW5kaWNhdGVzIHRoZSBlbmQgd2hpY2ggd2lsbCBub3QgYmUgcHJvY2Vzc2VkLiBUaGUgaW5wdXQgZG9lcyBub3QgZXhjZWVkIDEsMDAwIGxpbmVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IG91dCBpbiBlYWNoIGxpbmUgdGhlIGxhcmdlc3QgcHJpbWUgbnVtYmVyIGZvdW5kIGluIGVhY2ggaW5wdXQgc3RyaW5nLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==