시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 653 139 75 17.606%

문제

양의 정수로 이루어진 길이가 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+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIHhcdWI3N2NcdWJhNzQgJnF1b3Q7U2hvcnRlc3QgcHJpbWVkIHN1YnNlcXVlbmNlIGlzIGxlbmd0aCB4OiZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YWRmOCBcdWMyMThcdWM1ZjQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMThjXHVjMjE4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YmE3NCwgXHViYTNjXHVjODAwIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxOGNcdWMyMTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O1RoaXMgc2VxdWVuY2UgaXMgYW50aS1wcmltZWQuJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2ODg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHJpbWVkIFNlcXVlbmNlcyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBzZXF1ZW5jZSBvZiBwb3NpdGl2ZSBpbnRlZ2VycyBvZiBsZW5ndGggbiwgd2UgZGVmaW5lIGEgcHJpbWVkIHN1YnNlcXVlbmNlIGFzIGEgY29uc2VjdXRpdmUgc3Vic2VxdWVuY2Ugb2YgbGVuZ3RoIGF0IGxlYXN0IHR3byB0aGF0IHN1bXMgdG8gYSBwcmltZSBudW1iZXIgZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvIHR3by48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGdpdmVuIHRoZSBzZXF1ZW5jZTo8XC9wPlxyXG5cclxuPHA+MyA1IDYgMyA4PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSB0d28gcHJpbWVkIHN1YnNlcXVlbmNlcyBvZiBsZW5ndGggMiAoNSArIDYgPSAxMSBhbmQgMyArIDggPSAxMSksIG9uZSBwcmltZWQgc3Vic2VxdWVuY2Ugb2YgbGVuZ3RoIDMgKDYgKyAzICsgOCA9IDE3KSwgYW5kIG9uZSBwcmltZWQgc3Vic2VxdWVuY2Ugb2YgbGVuZ3RoIDQgKDMgKyA1ICsgNiArIDMgPSAxNykuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiBhIHNlcmllcyBvZiB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBjb25zaXN0cyBvZiBhbiBpbnRlZ2VyIHQgKDEgJmxlOyB0ICZsZTsgMjApLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuPFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIG9uZSBsaW5lLiBUaGUgbGluZSBiZWdpbnMgd2l0aCB0aGUgaW50ZWdlciBuLCAwICZsdDsgbiAmbGU7IDEwMDAwLCBmb2xsb3dlZCBieSBuIG5vbi1uZWdhdGl2ZSBudW1iZXJzIGxlc3MgdGhhbiAxMDAwMCBjb21wcmlzaW5nIHRoZSBzZXF1ZW5jZS4gWW91IHNob3VsZCBub3RlIHRoYXQgODAlIG9mIHRoZSB0ZXN0IGNhc2VzIHdpbGwgaGF2ZSBhdCBtb3N0IDEwMDAgbnVtYmVycyBpbiB0aGUgc2VxdWVuY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggc2VxdWVuY2UsIHByaW50IHRoZSAmcXVvdDtTaG9ydGVzdCBwcmltZWQgc3Vic2VxdWVuY2UgaXMgbGVuZ3RoIHg6JnF1b3Q7LCB3aGVyZSB4IGlzIHRoZSBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IHByaW1lZCBzdWJzZXF1ZW5jZSwgZm9sbG93ZWQgYnkgdGhlIHNob3J0ZXN0IHByaW1lZCBzdWJzZXF1ZW5jZSwgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHN1Y2ggc2VxdWVuY2VzLCBwcmludCB0aGUgb25lIHRoYXQgb2NjdXJzIGZpcnN0LjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBhcmUgbm8gc3VjaCBzZXF1ZW5jZXMsIHByaW50ICZxdW90O1RoaXMgc2VxdWVuY2UgaXMgYW50aS1wcmltZWQuJnF1b3Q7LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==