Recently, at the center of the Chess Kingdom, a king has created a challenge for his bravest knights. In the large courtyard is a square gemstone floor of size ~n \times n~, divided into small squares. Each square can either contain a mysterious black crystal (denoted as #) — a material that can absorb all sunlight, or a transparent square (denoted as .).

The knights stand in turn at the four walls of the courtyard: North, South, West, or East, holding the legendary Prism of Illumination. By adjusting the prism, the knight can project a beam of parallel light perpendicular to the walls:

• From the North wall, the beams shine down each column towards the South.

• From the South wall, the beams shoot up each column towards the North.

• From the West wall, the beams sweep across each row towards the East.

• From the East wall, the beams sweep across each row towards the West.

When a beam encounters at least one crystal (~\#~) on its path, it creates a shadow projected onto the opposite wall at the corresponding column position (for North/South) or row (for West/East). The knight records a shadow for that position. If no crystal is encountered, that position remains brightly lit.

Legend has it that the winning knight will be the one who finds the "brightest" viewpoint — meaning the direction to shoot the beam where the number of shaded positions is minimal.

Input

The first line contains a positive integer ~T~ (~1 \le T \le 100~) — the number of test cases.

The first line of each test case contains a positive integer ~n~ (~1 \le n \le 100~) — the size of the gemstone floor.

The next ~n~ lines of each test case consist of a string of length ~n~ made up of two characters (~\#~ or ~.~) — the squares of the gemstone floor.

Output

For each test case, print on one line the minimum number of shaded positions.

Sample Input 1

2
3
###
#.#
...
4
#...
.#..
..#.
...#

Sample Output 1

2
4

Notes

In the first example, if The knights shoots the beam from the West, the number of shaded positions is ~2~.

If The knights shoots the beam from the South, the number of shaded positions is ~3~.

From the east:

From the north: