페그 솔리테어

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

핀은 수평이나 수직으로 인접한 핀을 뛰어넘어 그 핀의 바로 다음 칸으로 이동하는 것만 허용된다. 뛰어넘어 도착할 칸은 비어 있는 구멍이어야 하고, 뛰어넘긴 핀은 게임판에서 빠진다.

게임판에 핀이 꽂혀 있는 상태가 주어진다. 핀을 적절히 움직여 게임판에 남는 핀의 개수를 최소로 만들고, 그 개수를 만드는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. ($1 \le N \le 100$)

각 테스트 케이스는 게임판의 처음 상태를 나타내는 다섯 줄이고, 각 줄은 아홉 글자다. 게임판 모양은 모든 테스트 케이스에서 같다. 첫째 줄과 다섯째 줄은 넷째 칸부터 여섯째 칸까지 세 칸에만 구멍이 있고, 둘째 줄부터 넷째 줄까지는 아홉 칸 모두 구멍이 있다.

.는 빈 칸, o는 핀이 꽂혀 있는 칸, #는 구멍이 없는 칸이다. 핀의 개수는 최대 8이다. 테스트 케이스 사이는 빈 줄로 구분한다.

각 테스트 케이스마다 정수 두 개를 공백으로 구분해 한 줄에 출력한다. 첫 번째 정수는 핀을 움직여 남길 수 있는 핀의 최소 개수이고, 두 번째 정수는 그 개수를 만드는 데 필요한 최소 이동 횟수다.