Independent Architecture

Interview

Time limit1sMemory limit128 MB

Summary

Count the wall cells plus the empty cells enclosed by the single closed wall loop in each grid.

Level: Medium4 of 10
Topics: BFS, Matrix
Solved: No attempts yet

Problem

Monika is an artist and an architect. Every building she designs is a work of art. She is full of passion and creates one design after another, but she always builds only her own ideas and never designs buildings to order.

Even so, one has to make a living. Monika decided to sell her designs to interested buyers without giving up her principles: anyone who wants to buy a design must hope that she has already created something matching their needs. To make it easier to search her collection for what a client wants, Monika would like to quickly compute the area of each building she has designed.

Every design is a regular square grid with $N$ rows and $N$ columns, containing $N^2$ cells. Each cell is either an empty cell or a wall of the building. Empty cells are marked with a dot (.) and walls are marked with a hash (#).

The walls of a building form a single closed loop with no self-intersections: every wall cell is adjacent (up, down, left, or right) to exactly two other wall cells, and those two cells are its neighbours along the loop that outlines the building.

Given a building's design, compute its area: the total number of wall cells plus the number of empty cells enclosed inside the building.

Input

The first line contains a natural number $Z$ ( $1 \le Z \le 10$ ), the number of test sets. The test sets follow.

The first line of each test set contains a natural number $N$ ( $3 \le N \le 1000$ ), the size of the design. Each of the next $N$ lines contains one row of the design, written with the characters described above.

Output

For each test set, print the area of the building on its own line.

Examples4

Example 1

Input

2
7
.......
#######
#.....#
#.###.#
###.###
.......
.......
3
###
#.#
###

Expected output

27
9

Example 2
Input
```
1
3
###
#.#
###
```
Expected output
```
9
```
Example 3
Input
```
1
5
#####
#...#
#...#
#...#
#####
```
Expected output
```
25
```
Example 4
Input
```
1
5
.....
.###.
.#.#.
.###.
.....
```
Expected output
```
9
```