시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 199 89 60 40.541%

문제

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

핀은 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동할 수 있다. 인접한 핀의 다음 칸은 비어있어야 한다. 그리고 그 인접한 핀은 제거한다.

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

입력

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

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

출력

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

예제 입력

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

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

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

예제 출력

1 3
1 7
1 7

힌트