Problem Description

There is a square grid of size $N$ rows and $N$ columns. The cell at the $i$-th row from the top and the $j$-th column from the left is denoted as $(i, j)$.

Initially, each cell is either white or black. The initial color of the grid is given as a square array of characters $a_{ij}$ ($1 \leq i, j \leq N$). If the cell $(i, j)$ is white, then $a_{ij}$ is ., and if it is black, then $a_{ij}$ is #.

You are developing a robot that can repaint the grid. The robot can repeatedly perform the following operation:

• Choose integers $i$ and $j$ ($1 \leq i, j \leq N$). Memorize the colors of the cells $(i, 1)$, $(i, 2)$, ..., $(i, N)$ as $c_1$, $c_2$, ..., $c_N$. Then, repaint the cells $(1, j)$, $(2, j)$, ..., $(N, j)$ with the colors $c_1$, $c_2$, ..., $c_N$.

Your goal is to make all cells black. Determine if it is possible to make all cells black, and if so, find the minimum number of operations required.

Input Format

The input is given from the standard input in the following format:

$N$ $a_{11}$ ... $a_{1N}$ : $a_{N1}$ ... $a_{NN}$

Output Format

If it is possible to make all cells black, output the minimum number of operations required. If it is not possible, output -1 instead.

Sample Input and Output

Sample Input #1

2
#.
.#

Sample Output #1

3

Sample Input #2

2
..
..

Sample Output #2

-1

Sample Input #3

2
##
##

Sample Output #3

0

Sample Input #4

3
.#.
###
.#.

Sample Output #4

2

Sample Input #5

3
...
.#.
...

Sample Output #5

5

Notes/Hints

Constraints

• $2 \leq N \leq 500$
• $a_{ij}$ is either . or #.

Partial Points

• For $300$ points worth of test cases, $N \leq 3$ holds.

Sample Explanation 1

For example, by performing the operations as follows, the grid's colors change as shown in the figure:
- Choose $i = 1$, $j = 2$ and perform the operation.
- Choose $i = 1$, $j = 1$ and perform the operation.
- Choose $i = 1$, $j = 2$ and perform the operation.

见题面 Input 部分

见题面 Output 部分