시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 581 261 179 42.926%

문제

페그 솔리테어는 구멍이 뚤려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다.

핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다.

현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이 때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 1 ≤ N ≤ 100이 주어진다. 각 테스트 케이스는 게임판의 초기 상태이다.

게임판은 모두 같은 모양을 가진다. (예제 참고) '.'는 빈 칸, 'o'는 핀이 꽂혀있는 칸, '#'는 구멍이 없는 칸이다. 핀의 개수는 최대 8이며, 각 테스트 케이스는 빈 줄로 구분되어져 있다.

출력

각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다.

예제 입력 1

3
###...###
..oo.....
.....oo..
.........
###...###

###...###
..oo.o...
...o.oo..
...oo....
###...###

###o..###
.o.oo....
o.o......
.o.o.....
###...###

예제 출력 1

1 3
1 7
1 7
W3sicHJvYmxlbV9pZCI6IjkyMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzOThcdWFkZjggXHVjMTk0XHViOWFjXHVkMTRjXHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzOThcdWFkZjggXHVjMTk0XHViOWFjXHVkMTRjXHVjNWI0XHViMjk0IFx1YWQ2Y1x1YmE0ZFx1Yzc3NCBcdWI2YTRcdWI4MjRcdWM3ODhcdWIyOTQgXHVjNzc0XHVjYzI4XHVjNmQwIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1YzVkMFx1YzExYyBcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVhZDZjXHViYTRkXHVjNWQwXHViMjk0IFx1ZDU0MFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVhZjQyXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU0MFx1Yzc0MCBcdWMyMThcdWQzYzksIFx1YzIxOFx1YzljMSBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1ZDU0MFx1Yzc0NCBcdWI2ZjBcdWM1YjRcdWIxMThcdWM1YjRcdWMxMWMgXHVhZGY4IFx1ZDU0MFx1Yzc1OCBcdWIyZTRcdWM3NGMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWI5Y2MgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LiBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVkNTQwXHVjNzU4IFx1YjJlNFx1Yzc0YyBcdWNlNzhcdWM3NDAgXHViZTQ0XHVjNWI0XHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCBcdWFkZjggXHVjNzc4XHVjODExXHVkNTVjIFx1ZDU0MFx1Yzc0MCBcdWM4MWNcdWFjNzBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHVhZjQyXHVkNjAwXHVjNzg4XHViMjk0IFx1ZDU0MFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWQ1NDBcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YzZjMFx1YzljMVx1YzVlY1x1YzExYyBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1ZDU0MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVhZGY4XHViODA3XHVhYzhjIFx1YjBhOFx1YWUzMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM3NzRcdWIzZDlcdWQ2OWZcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IDEgJmxlOyBOICZsZTsgMTAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YmFhOFx1YzU5MVx1Yzc0NCBcdWFjMDBcdWM5YzRcdWIyZTQuIChcdWM2MDhcdWM4MWMgXHVjYzM4XHVhY2UwKSAmIzM5Oy4mIzM5O1x1YjI5NCBcdWJlNDggXHVjZTc4LCAmIzM5O28mIzM5O1x1YjI5NCBcdWQ1NDBcdWM3NzQgXHVhZjQyXHVkNjAwXHVjNzg4XHViMjk0IFx1Y2U3OCwgJiMzOTsjJiMzOTtcdWIyOTQgXHVhZDZjXHViYTRkXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWNlNzhcdWM3NzRcdWIyZTQuIFx1ZDU0MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIDhcdWM3NzRcdWJhNzAsIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmU0OCBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDU0MFx1Yzc0NCBcdWM2YzBcdWM5YzFcdWM1ZWNcdWMxMWMgXHViMGE4XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTQwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM2NDAgXHVhZGY4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTIwNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBlZyBTb2xpdGFpcmUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBnYW1lIG9mIHBlZyBzb2xpdGFpcmUsIHBvcHVsYXIgYXQgdGhlIGNvdXJ0IG9mIHRoZSBGcmVuY2gga2luZyBMb3VpcyBYSVYsIGhhcyB0aGUgZm9sbG93aW5nIHJ1bGVzLiBHaXZlbiBhIHR3by1kaW1lbnNpb25hbCBib2FyZCB3aXRoIGEgbWVzaCBvZiBob2xlcywgZWFjaCBob2xlIGNhbiBjb250YWluIG9uZSBwZWcgKHBpbikuIFRoZSBvbmx5IGxlZ2FsIG1vdmUgb2YgYSBwZWcgaXMgYSB2ZXJ0aWNhbCBvciBob3Jpem9udGFsIGp1bXAgb3ZlciBhbiBhZGphY2VudCBwZWcgaW50byB0aGUgZW1wdHkgaG9sZSBuZXh0IHRvIHRoZSBqdW1wZWQgcGVnIGluIGxpbmUgd2l0aCBpdCwgd2hpY2ggaXMgdGhlbiByZW1vdmVkLiBUaGUgb3JpZ2luYWwgZ29hbCBvZiB0aGUgZ2FtZSB3YXMgdG8gbGVhdmUgYSBzaW5nbGUgcGVnIGluIHRoZSBwcmVkZWZpbmVkIHBvc2l0aW9uIG9uIHRoZSBib2FyZCBieSBwZXJmb3JtaW5nIG9ubHkgbGVnYWwgbW92ZXMuIE9idmlvdXNseSwgc3VjaCBhIHNvbHV0aW9uIGlzIHBvc3NpYmxlIG9ubHkgZm9yIGNlcnRhaW4gYm9hcmQgZm9ybXMgYW5kIHN0YXJ0aW5nIGNvblx1ZmIwMWd1cmF0aW9ucy4gVG8gZHJvcCB0aGlzIHJlc3RyaWN0aW9uLCB3ZSBzbGlnaHRseSByZWRlXHVmYjAxbmUgdGhlIHByb2JsZW06IEdpdmVuIHRoZSBzdGFydGluZyBjb25cdWZiMDFndXJhdGlvbiBvZiB0aGUgYm9hcmQsIGRldGVybWluZSB0aGUgbWluaW11bSBudW1iZXIgb2YgcGVncyB0aGF0IGNhbiBiZSBhY2hpZXZlZCBieSBtZWFucyBvZiBsZWdhbCBtb3ZlcyBhcyB3ZWxsIGFzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3ZlcyByZXF1aXJlZCB0byByZWFjaCB0aGF0IG51bWJlciBvZiBwZWdzPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgb25lIG51bWJlciwgMSAmbGU7IE4gJmxlOyAxMDAgd2hpY2ggcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIGRlc2NyaWJlZCBieSB0aGUgZm9sbG93aW5nIGxpbmVzIG9mIGlucHV0IHRoYXQgcmVwcmVzZW50IHRoZSBpbml0aWFsIHN0YXRlIG9mIHRoZSBzb2xpdGFpcmUgYm9hcmQuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcmVwcmVzZW50YXRpb24gJnJzcXVvOy4mcnNxdW87IGRlbm90ZXMgYW4gZW1wdHkgaG9sZSBhbmQgJnJzcXVvO28mcnNxdW87IGEgaG9sZSB3aXRoIGEgcGVnIGluIGl0LiAmcnNxdW87IyZyc3F1bzsgaW5kaWNhdGVzIGEgcGFydCBvZiB0aGUgYm9hcmQgd2l0aG91dCBhIGhvbGUuIEFsbCBib2FyZHMgaGF2ZSB0aGUgc2FtZSBzaGFwZSwgc2VlIHNhbXBsZSBpbnB1dCAodGhhdCBpbmNsdWRlcyBwb3NpdGlvbiBvZiBob2xlcykuIEluIGl0cyBpbml0aWFsIHN0YXRlLCB0aGUgYm9hcmQgY2FuIGNvbnRhaW4gYXQgbW9zdCA4IHBlZ3MuIFRoZXJlIGlzIGFuIGVtcHR5IGxpbmUgYmV0d2VlbiB0d28gY29uc2VjdXRpdmUgdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgYSBsaW5lIHdpdGggdHdvIG51bWJlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHdoaXRlc3BhY2UsIHdpdGggdGhlIGZpcnN0IG9uZSBkZW5vdGluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgcGVncyBhY2hpZXZhYmxlIGJ5IGxlZ2FsIG1vdmVzIHN0YXJ0aW5nIHdpdGggdGhlIGdpdmVuIGluaXRpYWwgc3RhdGUsIGFuZCB0aGUgc2Vjb25kIG9uZSBwcm92aWRpbmcgdGhlIG1pbmltdW0gcmVxdWlyZWQgbnVtYmVyIG9mIG1vdmVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==