시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 23 7 7 33.333%

문제

폴리큐브는 모서리의 길이가 1인 단위 정육면체를 면과 면끼리 붙여서 만든 입체이다. 아래 그림에서 왼쪽 아래 입체는 선과 선끼리 붙였기 때문에, 폴리큐브가 아니다.

폴리큐브를 이루는 정육면체의 중심은 모두 3차원 공간에 있고, 정수 좌표이다.

폴리큐브를 만들기 위해서 가장 처음 (0, 0, 0)에 있는 큐브부터 시작한다. 그 다음, 폴리큐브를 만드는 각 단계에서 다음 정육면체는 반드시 이전 정육면체와 면이 닿아야 한고, 지금까지 나오지 않은 정육면체이어야 한다. 예를 들어, 그림에서 왼쪽 위에 있는 폴리큐브는 아래와 같이 만들 수 있다.

(0,0,0) (0,0,1) (0,0,2) (0,0,3) (0,0,4)

그리고, 오른쪽 위에 있는 폴리큐브는 다음과 같이 만들 수 있다.

(0,0,0) (0,0,1) (0,1,1) (0,1,0) (1,0,0) (1,0,1) (1,1,1) (1,1,0)

폴리큐브는 단위 정육면체로 이루어져있기 때문에, 이것의 겉넓이은 모두 정수이다.

3차원 공간의 좌표가 주어질 때, 이것이 폴리큐브를 이루어지는지 구하고, 폴리큐브라면 겉넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 첫째 줄에는 점의 개수 P(1<=P<=100)가 주어진다. 그 다음줄부터 정육면체의 중심 좌표가 차례대로 한 줄에 8개씩 주어진다.

출력

각 테스트 케이스에 대해서 폴리큐브를 이룬다면 그것의 단면적을 출력하고, 아니라면 NO를 출력한 뒤에, 몇 번째 정육면체 폴리큐브를 이룰 수 없었는지를 출력한다. 첫 번째 정육면체는 1번이다.

예제 입력 1

4
5
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4
8
0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1
4
0,0,0 0,0,1 1,1,0 1,1,1
20
0,0,0 0,0,1 0,0,2 0,1,2 0,2,2 0,2,1 0,2,0 0,1,0
1,0,0 2,0,0 1,0,2 2,0,2 1,2,2 2,2,2 1,2,0 2,2,0
2,1,0 2,1,2 2,0,1 2,2,1

예제 출력 1

22
24
NO 3
72
W3sicHJvYmxlbV9pZCI6IjI3MDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWM3NTggXHVhYzg5XHViMTEzXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWIyOTQgXHViYWE4XHVjMTFjXHViOWFjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YjJlOFx1YzcwNCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWI5N2MgXHViYTc0XHVhY2ZjIFx1YmE3NFx1YjA3Y1x1YjlhYyBcdWJkOTlcdWM1ZWNcdWMxMWMgXHViOWNjXHViNGUwIFx1Yzc4NVx1Y2NiNFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Yzc4NVx1Y2NiNFx1YjI5NCBcdWMxMjBcdWFjZmMgXHVjMTIwXHViMDdjXHViOWFjIFx1YmQ5OVx1YzYwMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMDQlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDExXzA0XzQ3LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjQ2N3B4OyB3aWR0aDo1ODFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NDAgXHViYWE4XHViNDUwIDNcdWNjMjhcdWM2ZDAgXHVhY2Y1XHVhYzA0XHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2Y0XHViOWFjXHVkMDUwXHViZTBjXHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0YyAoMCwgMCwgMClcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDA1MFx1YmUwY1x1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWIyZTRcdWM3NGMgXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3NzRcdWM4MDQgXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHVjNjQwIFx1YmE3NFx1Yzc3NCBcdWIyZmZcdWM1NDRcdWM1N2MgXHVkNTVjXHVhY2UwLCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHViMDk4XHVjNjI0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwO1x1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWM2N2NcdWNhYmQgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+KDAsMCwwKSAoMCwwLDEpICgwLDAsMikgKDAsMCwzKSAoMCwwLDQpPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkM2Y0XHViOWFjXHVkMDUwXHViZTBjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPigwLDAsMCkgKDAsMCwxKSAoMCwxLDEpICgwLDEsMCkgKDEsMCwwKSAoMSwwLDEpICgxLDEsMSkgKDEsMSwwKTxcL3A+XHJcblxyXG48cD5cdWQzZjRcdWI5YWNcdWQwNTBcdWJlMGNcdWIyOTQgXHViMmU4XHVjNzA0IFx1YzgxNVx1YzcyMVx1YmE3NFx1Y2NiNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3NzRcdWFjODNcdWM3NTggXHVhYzg5XHViMTEzXHVjNzc0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjNcdWNjMjhcdWM2ZDAgXHVhY2Y1XHVhYzA0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWM3NzRcdWFjODNcdWM3NzQgXHVkM2Y0XHViOWFjXHVkMDUwXHViZTBjXHViOTdjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljMFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWFjZTAsIFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1Yjc3Y1x1YmE3NCBcdWFjODlcdWIxMTNcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSZsdDs9VCZsdDs9MSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggUCgxJmx0Oz1QJmx0Oz0xMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzkwNFx1YmQ4MFx1ZDEzMCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWM3NTggXHVjOTExXHVjMmVjIFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCA4XHVhYzFjXHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkM2Y0XHViOWFjXHVkMDUwXHViZTBjXHViOTdjIFx1Yzc3NFx1YjhlY1x1YjJlNFx1YmE3NCBcdWFkZjhcdWFjODNcdWM3NTggXHViMmU4XHViYTc0XHVjODAxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0IE5PXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWI0YTRcdWM1ZDAsIFx1YmE4NyBcdWJjODhcdWM5ZjggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0IFx1ZDNmNFx1YjlhY1x1ZDA1MFx1YmUwY1x1Yjk3YyBcdWM3NzRcdWI4ZjAgXHVjMjE4IFx1YzVjNlx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHViMjk0IDFcdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjcwOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFyZWEgb2YgUG9seWN1YmVzIiwiZGVzY3JpcHRpb24iOiI8cD5BIHBvbHljdWJlIGlzIGEgc29saWQgbWFkZSBieSBnbHVpbmcgdG9nZXRoZXIgdW5pdCBjdWJlcyAob25lIHVuaXQgb24gZWFjaCBlZGdlKSBvbiBvbmUgb3IgbW9yZSBmYWNlcy4gVGhlIGZpZ3VyZSBpbiB0aGUgbG93ZXItbGVmdCBpcyBub3QgYSBwb2x5Y3ViZSBiZWNhdXNlIHNvbWUgY3ViZXMgYXJlIGF0dGFjaGVkIGFsb25nIGFuIGVkZ2UuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMDQlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDExXzA0XzQ3LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjQ2N3B4OyB3aWR0aDo1ODFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCB0aGUgcG9seWN1YmUgd2lsbCBiZSBmb3JtZWQgZnJvbSB1bml0IGN1YmVzIGNlbnRlcmVkIGF0IGludGVnZXIgbGF0dGljZSBwb2ludHMgaW4gMy1zcGFjZS4gVGhlIHBvbHljdWJlIHdpbGwgYmUgYnVpbHQgdXAgb25lIGN1YmUgYXQgYSB0aW1lLCBzdGFydGluZyB3aXRoIGEgY3ViZSBjZW50ZXJlZCBhdCAoMCwwLDApLiBBdCBlYWNoIHN0ZXAgb2YgdGhlIHByb2Nlc3MgKGFmdGVyIHRoZSBmaXJzdCBjdWJlKSwgdGhlIG5leHQgY3ViZSBtdXN0IGhhdmUgYSBmYWNlIGluIGNvbW1vbiB3aXRoIGEgY3ViZSBwcmV2aW91c2x5IGluY2x1ZGVkIGFuZCBub3QgYmUgdGhlIHNhbWUgYXMgYSBibG9jayBwcmV2aW91c2x5IGluY2x1ZGVkLiBGb3IgZXhhbXBsZSwgYSAxLWJ5LTEtYnktNSBibG9jayAoYXMgc2hvd24gYWJvdmUgaW4gdGhlIHVwcGVyLWxlZnQgcG9seWN1YmUpIGNvdWxkIGJlIGJ1aWx0IHVwIGFzOjxcL3A+XHJcblxyXG48cD4oMCwwLDApICgwLDAsMSkgKDAsMCwyKSAoMCwwLDMpICgwLDAsNCk8XC9wPlxyXG5cclxuPHA+YW5kIGEgMi1ieS0yLWJ5LTIgY3ViZSAodXBwZXItcmlnaHQgZmlndXJlKSBjb3VsZCBiZSBidWlsdCBhczo8XC9wPlxyXG5cclxuPHA+KDAsMCwwKSAoMCwwLDEpICgwLDEsMSkgKDAsMSwgMCkgKDEsMCwwKSAoMSwwLDEpICgxLDEsMSkgKDEsMSwgMCk8XC9wPlxyXG5cclxuPHA+U2luY2UgdGhlIHN1cmZhY2Ugb2YgdGhlIHBvbHljdWJlIGlzIG1hZGUgdXAgb2YgdW5pdCBzcXVhcmVzLCBpdHMgYXJlYSBpcyBhbiBpbnRlZ2VyLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggdGFrZXMgYXMgaW5wdXQgYSBzZXF1ZW5jZSBvZiBpbnRlZ2VyIGxhdHRpY2UgcG9pbnRzIGluIDMtc3BhY2UgYW5kIGRldGVybWluZXMgd2hldGhlciBpcyBjb3JyZWN0bHkgZm9ybXMgYSBwb2x5Y3ViZSBhbmQsIGlmIHNvLCB3aGF0IHRoZSBzdXJmYWNlIGFyZWEgb2YgdGhlIHBvbHljdWJlIGlzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOLCAoMSAmbGU7IE4gJmxlOyAxMDAwKSB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBtdWx0aXBsZSBsaW5lcyBvZiBpbnB1dC4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBwb2ludHMgUCwgKDEgPSBQID0gMTAwKSBpbiB0aGUgcHJvYmxlbSBpbnN0YW5jZS4gRWFjaCBzdWNjZWVkaW5nIGxpbmUgY29udGFpbnMgdGhlIGNlbnRlcnMgb2YgdGhlIGN1YmVzLCBlaWdodCB0byBhIGxpbmUgKGV4Y2VwdCBwb3NzaWJseSBmb3IgdGhlIGxhc3QgbGluZSkuIEVhY2ggY2VudGVyIGlzIGdpdmVuIGFzIDMgaW50ZWdlcnMsIHNlcGFyYXRlZCBieSBjb21tYXMuIFRoZSBwb2ludHMgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgeW91IHNob3VsZCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlczogVGhlIGRhdGEgc2V0IG51bWJlciBhcyBhIGRlY2ltYWwgaW50ZWdlciAoc3RhcnQgY291bnRpbmcgYXQgb25lKSwgYSBzcGFjZSBhbmQgdGhlIHN1cmZhY2UgYXJlYSBvZiB0aGUgcG9seWN1YmUgaWYgaXQgaXMgY29ycmVjdGx5IGZvcm1lZCwgT1IsIGlmIGl0IGlzIG5vdCBjb3JyZWN0bHkgZm9ybWVkLCB0aGUgc3RyaW5nICZsZHF1bztOTyZyZHF1bzsgYSBzcGFjZSBhbmQgdGhlIGluZGV4IChzdGFydGluZyB3aXRoIDEpIG9mIHRoZSBmaXJzdCBjdWJlIHdoaWNoIGRvZXMgbm90IHNoYXJlIGEgZmFjZSB3aXRoIGEgcHJldmlvdXMgY3ViZS4gTm90ZSB0aGF0IHRoZSBzdXJmYWNlIGFyZWEgaW5jbHVkZXMgdGhlIGFyZWEgb2YgYW55IGluY2x1ZGVkIGhvbGVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==