시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 841 385 244 45.018%

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 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
W3sicHJvYmxlbV9pZCI6IjkyMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzOThcdWFkZjggXHVjMTk0XHViOWFjXHVkMTRjXHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzOThcdWFkZjggXHVjMTk0XHViOWFjXHVkMTRjXHVjNWI0XHViMjk0IFx1YWQ2Y1x1YmE0ZFx1Yzc3NCBcdWI2YTRcdWI4MjRcdWM3ODhcdWIyOTQgXHVjNzc0XHVjYzI4XHVjNmQwIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1YzVkMFx1YzExYyBcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVhZDZjXHViYTRkXHVjNWQwXHViMjk0IFx1ZDU0MFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVhZjQyXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU0MFx1Yzc0MCBcdWMyMThcdWQzYzksIFx1YzIxOFx1YzljMSBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1ZDU0MFx1Yzc0NCBcdWI2ZjBcdWM1YjRcdWIxMThcdWM1YjRcdWMxMWMgXHVhZGY4IFx1ZDU0MFx1Yzc1OCBcdWIyZTRcdWM3NGMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWI5Y2MgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LiBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVkNTQwXHVjNzU4IFx1YjJlNFx1Yzc0YyBcdWNlNzhcdWM3NDAgXHViZTQ0XHVjNWI0XHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCBcdWFkZjggXHVjNzc4XHVjODExXHVkNTVjIFx1ZDU0MFx1Yzc0MCBcdWM4MWNcdWFjNzBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHVhZjQyXHVkNjAwXHVjNzg4XHViMjk0IFx1ZDU0MFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDU0MFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjNmMwXHVjOWMxXHVjNWVjXHVjMTFjIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1YzVkMCBcdWIwYThcdWM1NDRcdWM3ODhcdWIyOTQgXHVkNTQwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWFkZjhcdWI4MDdcdWFjOGMgXHViMGE4XHVhZTMwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1Yzc3NFx1YjNkOVx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggMSAmbGU7IE4gJmxlOyAxMDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVkMzEwXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM3NDAgXHViYWE4XHVjNTkxXHVjNzQ0IFx1YWMwMFx1YzljNFx1YjJlNC4gKFx1YzYwOFx1YzgxYyBcdWNjMzhcdWFjZTApICYjMzk7LiYjMzk7XHViMjk0IFx1YmU0OCBcdWNlNzgsICYjMzk7byYjMzk7XHViMjk0IFx1ZDU0MFx1Yzc3NCBcdWFmNDJcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjZTc4LCAmIzM5OyMmIzM5O1x1YjI5NCBcdWFkNmNcdWJhNGRcdWM3NzQgXHVjNWM2XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YjJlNC4gXHVkNTQwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgOFx1Yzc3NFx1YmE3MCwgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkNTQwXHVjNzQ0IFx1YzZjMFx1YzljMVx1YzVlY1x1YzExYyBcdWIwYThcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NDBcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1YzY0MCBcdWFkZjggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM3NzRcdWIzZDkgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MjA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGVnIFNvbGl0YWlyZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGdhbWUgb2YgcGVnIHNvbGl0YWlyZSwgcG9wdWxhciBhdCB0aGUgY291cnQgb2YgdGhlIEZyZW5jaCBraW5nIExvdWlzIFhJViwgaGFzIHRoZSBmb2xsb3dpbmcgcnVsZXMuIEdpdmVuIGEgdHdvLWRpbWVuc2lvbmFsIGJvYXJkIHdpdGggYSBtZXNoIG9mIGhvbGVzLCBlYWNoIGhvbGUgY2FuIGNvbnRhaW4gb25lIHBlZyAocGluKS4gVGhlIG9ubHkgbGVnYWwgbW92ZSBvZiBhIHBlZyBpcyBhIHZlcnRpY2FsIG9yIGhvcml6b250YWwganVtcCBvdmVyIGFuIGFkamFjZW50IHBlZyBpbnRvIHRoZSBlbXB0eSBob2xlIG5leHQgdG8gdGhlIGp1bXBlZCBwZWcgaW4gbGluZSB3aXRoIGl0LCB3aGljaCBpcyB0aGVuIHJlbW92ZWQuIFRoZSBvcmlnaW5hbCBnb2FsIG9mIHRoZSBnYW1lIHdhcyB0byBsZWF2ZSBhIHNpbmdsZSBwZWcgaW4gdGhlIHByZWRlZmluZWQgcG9zaXRpb24gb24gdGhlIGJvYXJkIGJ5IHBlcmZvcm1pbmcgb25seSBsZWdhbCBtb3Zlcy4gT2J2aW91c2x5LCBzdWNoIGEgc29sdXRpb24gaXMgcG9zc2libGUgb25seSBmb3IgY2VydGFpbiBib2FyZCBmb3JtcyBhbmQgc3RhcnRpbmcgY29uXHVmYjAxZ3VyYXRpb25zLiBUbyBkcm9wIHRoaXMgcmVzdHJpY3Rpb24sIHdlIHNsaWdodGx5IHJlZGVcdWZiMDFuZSB0aGUgcHJvYmxlbTogR2l2ZW4gdGhlIHN0YXJ0aW5nIGNvblx1ZmIwMWd1cmF0aW9uIG9mIHRoZSBib2FyZCwgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBwZWdzIHRoYXQgY2FuIGJlIGFjaGlldmVkIGJ5IG1lYW5zIG9mIGxlZ2FsIG1vdmVzIGFzIHdlbGwgYXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIHJlcXVpcmVkIHRvIHJlYWNoIHRoYXQgbnVtYmVyIG9mIHBlZ3M8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBvbmUgbnVtYmVyLCAxICZsZTsgTiAmbGU7IDEwMCB3aGljaCByZXByZXNlbnRzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgZGVzY3JpYmVkIGJ5IHRoZSBmb2xsb3dpbmcgbGluZXMgb2YgaW5wdXQgdGhhdCByZXByZXNlbnQgdGhlIGluaXRpYWwgc3RhdGUgb2YgdGhlIHNvbGl0YWlyZSBib2FyZC48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyByZXByZXNlbnRhdGlvbiAmcnNxdW87LiZyc3F1bzsgZGVub3RlcyBhbiBlbXB0eSBob2xlIGFuZCAmcnNxdW87byZyc3F1bzsgYSBob2xlIHdpdGggYSBwZWcgaW4gaXQuICZyc3F1bzsjJnJzcXVvOyBpbmRpY2F0ZXMgYSBwYXJ0IG9mIHRoZSBib2FyZCB3aXRob3V0IGEgaG9sZS4gQWxsIGJvYXJkcyBoYXZlIHRoZSBzYW1lIHNoYXBlLCBzZWUgc2FtcGxlIGlucHV0ICh0aGF0IGluY2x1ZGVzIHBvc2l0aW9uIG9mIGhvbGVzKS4gSW4gaXRzIGluaXRpYWwgc3RhdGUsIHRoZSBib2FyZCBjYW4gY29udGFpbiBhdCBtb3N0IDggcGVncy4gVGhlcmUgaXMgYW4gZW1wdHkgbGluZSBiZXR3ZWVuIHR3byBjb25zZWN1dGl2ZSB0ZXN0IGNhc2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSB5b3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBhIGxpbmUgd2l0aCB0d28gbnVtYmVycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgd2hpdGVzcGFjZSwgd2l0aCB0aGUgZmlyc3Qgb25lIGRlbm90aW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBwZWdzIGFjaGlldmFibGUgYnkgbGVnYWwgbW92ZXMgc3RhcnRpbmcgd2l0aCB0aGUgZ2l2ZW4gaW5pdGlhbCBzdGF0ZSwgYW5kIHRoZSBzZWNvbmQgb25lIHByb3ZpZGluZyB0aGUgbWluaW11bSByZXF1aXJlZCBudW1iZXIgb2YgbW92ZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d