시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 651 138 74 17.412%

문제

양의 정수로 이루어진 길이가 n인 수열이 있다. 소수 부분 수열이란 길이가 적어도 2이면서, 합이 2보다 크거나 같은 소수가 되는 연속 부분 수열이다.

예를 들어, 수열이 [3, 5, 6, 3, 8] 일 때, 길이가 2인 소수 부분 수열이 두 개(5 + 6 = 11, 3 + 8 = 11)이 있고, 길이가 3인 소수 부분 수열은 1개 (6 + 3 + 8 = 17), 길이가 4인 소수 부분 수열은 1개 (3 + 5 + 6 + 3 = 17) 가 있다.

수열이 주어졌을 때, 길이가 가장 짧은 소수 부분 수열을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 t (1 ≤ t ≤ 20) 가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 줄의 첫 번째 정수 n은 (0 < n ≤ 10000) 수열의 길이이다. 다음에 주어지는 음이 아닌 정수 n개는 수열의 원소이다. 수열의 원소는 10000보다 작은 정수이다.

출력

각 테스트 케이스마다 가장 짧은 소수 부분 수열의 길이가 x라면 "Shortest primed subsequence is length x:"를 출력하고, 그 수열 공백으로 구분해 출력한다. 가장 짧은 소수 부분 수열이 여러가지면, 먼저 나오는 것을 출력한다.

소수 부분 수열이 없는 경우에는 "This sequence is anti-primed."를 출력한다.

예제 입력 1

3
5 3 5 6 3 8
5 6 4 5 4 12
21 15 17 16 32 28 22 26 30 34 29 31 20 24 18 33 35 25 27 23 19 21

예제 출력 1

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.

힌트

W3sicHJvYmxlbV9pZCI6IjY4ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0XHVhYzAwIG5cdWM3NzggXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3ODAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzgwMVx1YzViNFx1YjNjNCAyXHVjNzc0XHViYTc0XHVjMTFjLCBcdWQ1NjlcdWM3NzQgMlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWI0MThcdWIyOTQgXHVjNWYwXHVjMThkIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzIxOFx1YzVmNFx1Yzc3NCBbMywgNSwgNiwgMywgOF0gXHVjNzdjIFx1YjU0YywgXHVhZTM4XHVjNzc0XHVhYzAwIDJcdWM3NzggXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHViNDUwIFx1YWMxYyg1ICsgNiA9IDExLCAzICsgOCA9IDExKVx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YWMwMCAzXHVjNzc4IFx1YzE4Y1x1YzIxOCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQwIDFcdWFjMWMgKDYgKyAzICsgOCA9IDE3KSwgXHVhZTM4XHVjNzc0XHVhYzAwIDRcdWM3NzggXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDAgMVx1YWMxYyAoMyArIDUgKyA2ICsgMyA9IDE3KSBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCB0ICgxICZsZTsgdCAmbGU7IDIwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzkwNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOCBuXHVjNzQwICgwICZsdDsgbiAmbGU7IDEwMDAwKSBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4IG5cdWFjMWNcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yzc3NFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjI5NCAxMDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIHhcdWI3N2NcdWJhNzQgJnF1b3Q7U2hvcnRlc3QgcHJpbWVkIHN1YnNlcXVlbmNlIGlzIGxlbmd0aCB4OiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YWRmOCBcdWMyMThcdWM1ZjQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViYTc0LCBcdWJhM2NcdWM4MDAgXHViMDk4XHVjNjI0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE4Y1x1YzIxOCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7VGhpcyBzZXF1ZW5jZSBpcyBhbnRpLXByaW1lZC4mcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY4ODQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmltZWQgU2VxdWVuY2VzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHNlcXVlbmNlIG9mIHBvc2l0aXZlIGludGVnZXJzIG9mIGxlbmd0aCBuLCB3ZSBkZWZpbmUgYSBwcmltZWQgc3Vic2VxdWVuY2UgYXMgYSBjb25zZWN1dGl2ZSBzdWJzZXF1ZW5jZSBvZiBsZW5ndGggYXQgbGVhc3QgdHdvIHRoYXQgc3VtcyB0byBhIHByaW1lIG51bWJlciBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdHdvLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgZ2l2ZW4gdGhlIHNlcXVlbmNlOjxcL3A+XHJcblxyXG48cD4zIDUgNiAzIDg8XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIHR3byBwcmltZWQgc3Vic2VxdWVuY2VzIG9mIGxlbmd0aCAyICg1ICsgNiA9IDExIGFuZCAzICsgOCA9IDExKSwgb25lIHByaW1lZCBzdWJzZXF1ZW5jZSBvZiBsZW5ndGggMyAoNiArIDMgKyA4ID0gMTcpLCBhbmQgb25lIHByaW1lZCBzdWJzZXF1ZW5jZSBvZiBsZW5ndGggNCAoMyArIDUgKyA2ICsgMyA9IDE3KS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIGEgc2VyaWVzIG9mIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIGNvbnNpc3RzIG9mIGFuIGludGVnZXIgdCAoMSAmbGU7IHQgJmxlOyAyMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy48XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2Ygb25lIGxpbmUuIFRoZSBsaW5lIGJlZ2lucyB3aXRoIHRoZSBpbnRlZ2VyIG4sIDAgJmx0OyBuICZsZTsgMTAwMDAsIGZvbGxvd2VkIGJ5IG4gbm9uLW5lZ2F0aXZlIG51bWJlcnMgbGVzcyB0aGFuIDEwMDAwIGNvbXByaXNpbmcgdGhlIHNlcXVlbmNlLiBZb3Ugc2hvdWxkIG5vdGUgdGhhdCA4MCUgb2YgdGhlIHRlc3QgY2FzZXMgd2lsbCBoYXZlIGF0IG1vc3QgMTAwMCBudW1iZXJzIGluIHRoZSBzZXF1ZW5jZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBzZXF1ZW5jZSwgcHJpbnQgdGhlICZxdW90O1Nob3J0ZXN0IHByaW1lZCBzdWJzZXF1ZW5jZSBpcyBsZW5ndGggeDomcXVvdDssIHdoZXJlIHggaXMgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgcHJpbWVkIHN1YnNlcXVlbmNlLCBmb2xsb3dlZCBieSB0aGUgc2hvcnRlc3QgcHJpbWVkIHN1YnNlcXVlbmNlLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgc3VjaCBzZXF1ZW5jZXMsIHByaW50IHRoZSBvbmUgdGhhdCBvY2N1cnMgZmlyc3QuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBubyBzdWNoIHNlcXVlbmNlcywgcHJpbnQgJnF1b3Q7VGhpcyBzZXF1ZW5jZSBpcyBhbnRpLXByaW1lZC4mcXVvdDsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d