Minesweeper

You are given an N x N board. Border cells contain no mines, and each border cell contains a digit. The digit is the number of mines among the cells adjacent to it in the eight directions.

Every non-border cell is written as #, and some of those cells may contain mines. Place mines so that every border digit matches the number of adjacent mines. Find the maximum number of mines that can be placed on the board.

The first line contains the number of test cases T.

For each test case, the first line contains the board size N. The next N lines each contain a string of length N describing the board. N is between 1 and 100, inclusive.

For each test case, print the maximum number of mines that can be placed on the board, one answer per line.