Flood-It

Flood-It은 스마트폰에서 인기 있는 1인용 게임이다. $n \times n$ 크기의 타일 판이 주어지고, 각 타일에는 1부터 6까지 번호가 붙은 여섯 가지 색 중 하나가 칠해져 있다. 각 타일은 북, 남, 동, 서 네 방향으로 최대 네 개의 타일과 맞닿는다. 어떤 타일의 색이 원점(왼쪽 위 모서리 타일)의 색과 같고, 그 색의 타일만 지나서 원점까지 가는 경로가 있으면 그 타일은 원점과 연결되어 있다.

한 번의 이동은 여섯 가지 색 중 하나를 고르는 것이다. 색을 고르면 원점과 연결된 타일이 모두 고른 색으로 바뀐다. 게임은 모든 타일의 색이 같아질 때까지 이어지고, 되도록 적은 횟수로 모든 타일을 같은 색으로 만드는 것이 목표다.

최적의 이동을 찾는 문제가 매우 어렵다는 사실은 이미 증명됐다. 이 문제에서는 아래의 단순한 그리디 전략이 얼마나 잘 동작하는지 시뮬레이션한다.

• 매 이동마다 원점과 연결되는 타일의 수가 가장 많아지는 색을 고른다.
• 그런 색이 여럿이면 번호가 가장 작은 색을 고른다.

처음부터 모든 타일의 색이 같으면 이동은 한 번도 필요하지 않다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 개수를 나타내는 정수 하나가 주어지고, 이 값은 20 이하다. 각 테스트 케이스의 첫 줄에는 정수 $n$ $(1 \le n \le 20)$이 주어진다. 이어지는 $n$개의 줄에는 각각 문자 $n$개가 주어져 $n \times n$ 판의 처음 색을 나타낸다. 각 색은 1부터 6까지의 숫자 하나로 표시된다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 줄에는 모든 타일을 같은 색으로 만드는 데 필요한 이동 횟수를 출력한다. 둘째 줄에는 공백 하나로 구분한 정수 6개를 출력한다. $i$번째 정수는 게임에서 색 $i$를 고른 횟수다.