Stake Your Claim

Two players, $0$ and $1$, play on an $n \times n$ board. Some squares already hold a 0 or a 1, and the rest are empty. The players take turns, starting with player $0$; on a turn, the current player writes their own number into one empty square. Play continues until the board is full.

When the board is full, each player's score is the size of the largest connected region of that player's number. A region is connected if you can travel between any two of its squares using only up, down, left, and right steps between squares holding the same number; diagonal steps do not connect squares. The player with the higher score wins and is awarded the difference between the two scores.

It is the current player's turn. The current player is player $0$ when the board holds an equal number of 0s and 1s, and player $1$ when it holds exactly one more 0 than 1. Assuming both players play optimally from now on, determine the best square for the current player to play and the best point total they can achieve, namely their own final score minus the opponent's final score (which may be negative).

The input contains several test cases.

Each test case begins with a line containing a positive integer $n$ ($n \le 8$), the size of the board. The next $n$ lines describe the board from row $0$ downward; each line has $n$ characters, each of which is 0, 1, or . (an empty square), with column $0$ first. The board holds either the same number of 0s and 1s or exactly one more 0 than 1, and it has between $1$ and $10$ empty squares.

A line containing a single 0 follows the last test case and must not be processed.

For each test case, print one line with the best move and the best point total for the current player, in the format (row,col) total, using $0$-based row and column indices. If several moves achieve the same best total, print the one that is smallest in lexicographic order of (row, col).