Flood-It

Flood-It is a popular one player game on many smart phones. The player is given an $n \times n$ board of tiles, and each tile has one of 6 colours numbered 1 to 6. Each tile touches up to 4 adjacent tiles in the north, south, east and west directions. A tile is connected to the origin (the tile in the upper left corner) if it has the same colour as the origin and there is a path to the origin that uses only tiles of that colour.

A player makes a move by choosing one of the 6 colours. After the choice is made, every tile connected to the origin changes to the chosen colour. The game runs until all tiles have the same colour, and the goal is to reach that state in as few moves as possible.

Finding the optimal moves has been proven to be a very hard problem. In this problem you simulate the simple greedy strategy below and report how it behaves.

• For each move, choose the colour that results in the largest number of tiles connected to the origin.
• If several colours tie, choose the lowest numbered colour.

If every tile already has the same colour, no move is needed.

The input consists of multiple test cases. The first line of input is a single integer, not more than 20, giving the number of test cases that follow. Each case starts with a line containing the integer $n$ $(1 \le n \le 20)$. The next $n$ lines each contain $n$ characters, giving the initial colours of the $n \times n$ board of tiles. Each colour is a digit from 1 to 6.

For each case, print two lines. The first line gives the number of moves needed to change all the tiles to the same colour. The second line gives 6 integers separated by a single space. The $i$th integer is the number of times colour $i$ is chosen as a move in the game.