Ga

The Dutch variant of the game of Go is called Ga. It is played on an $N \times N$ board, and all $N^2$ squares start out empty. Two players, White and Black, move in turn, and White starts. On a move, the player puts one or more stones of his own colour on empty squares, one stone per square, placing them one at a time. The first player who cannot move loses.

Two squares are adjacent if they touch horizontally, vertically or diagonally. A player must always place a stone on an empty square adjacent to a square that already holds a stone of his own colour. The very first stone a player puts on the board may go anywhere.

Local rules decide how many stones a player puts on the board during a move. In Volendam that number comes from a throw of the dice, and specialized shops there sell carved sets of dice, called gabbers, with different numbers of sides. Whatever the local rule is, an upper bound on the number of stones a player can place in one move is worth knowing.

Given the state of the board, find the largest number of stones White can put on it during his move.

The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

• A line with one integer $N$, the height and the width of the board ($2 \le N \le 100$).
• Then $N$ lines of $N$ characters each, describing the board. The character - is an empty square, w is a White stone and b is a Black stone.

Every board holds at least one White stone and at least one Black stone. The White stones placed so far follow the rules, and so do the Black ones.

For each test case, print one line with a single integer: the largest number of stones White can put on the given board in one move under the rules of Ga.