Sutomo 1 P2S1 Programming Contest

In the game of chess, rook is a piece that can move in any number of squares either horizontally or vertically but never pass through any pieces. In this problem, you will be given a few small chessboards(at most 4x4) that may contain walls which rooks cannot move through. The goal is to place as many rooks on the board as possible so that there won't be any two rooks that are attacking each other. The placement of the rooks is absolutely legal provided that there is no two rooks on the same row or column unless there is at least a wall seperating them.

The following example shows an empty 4x4 chessboard and the legal placement of the rooks.

.X.. RX.R
.... .R..
XX.. XXR.
.... R...

X = Wall
R = Rook
. = Empty tile

The first one is an empty 4x4 chessboard with three walls on it. The second one shows one of the legal placements and also the maximum number of rooks that can be placed.

Your task is to write a program that computes the maximum numbers of rook that can be placed on the chessboard in a legal configuration.

Input

The input contains more than one chessboard descriptions. The first line consists of a positive integer T(up to 50) indicating the number of descriptions. Each description begins with a positive integer N that indicates the size of the chessboard. The next N lines each describes a row of the chessboard, with '.' as an empty tile and 'X' as a wall.

Output

Print an integer in single line containing the maximum number of rooks that can be placed on the board in a legal configuration.

Example

Input:
2
4
.X..
...X
X...
..X.
3
...
...
...

Output:
6
3