题目描述

縦 $N$ 行、横 $N$ 列の正方形状のマス目があります。 上から $i$ 行目、左から $j$ 列目のマスを $(i,\ j)$ と表します。

最初、各マスは白か黒です。 最初のマス目の配色は、正方形状に並ぶ文字 $a_{ij}$ ($1\ <\ =\ i,\ j\ <\ =\ N$) として与えられます。 マス $(i,\ j)$ が白ならば $a_{ij}$ は . であり、黒ならば $a_{ij}$ は # です。

あなたは、マス目の配色を塗り替えるロボットを開発しています。 このロボットは次の操作を繰り返し行うことができます。

• 整数 $i$, $j$ ($1\ <\ =\ i,\ j\ <\ =\ N$) をそれぞれ自由に選ぶ。 マス $(i,\ 1)$, $(i,\ 2)$, $...$, $(i,\ N)$ の色をそれぞれ $c_1$, $c_2$, $...$, $c_N$ として記憶する。 その後、マス $(1,\ j)$, $(2,\ j)$, $...$, $(N,\ j)$ の色をそれぞれ $c_1$, $c_2$, $...$, $c_N$ で塗り替える。

あなたの目標は、すべてのマスを黒にすることです。 すべてのマスを黒にすることが可能か判定し、可能ならば必要な操作回数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すべてのマスを黒にすることが可能ならば、必要な操作回数の最小値を出力せよ。 不可能ならば、代わりに -1 を出力せよ。

2
#.
.#

3

2
..
..

-1

2
##
##

0

3
.#.
###
.#.

2

3
...
.#.
...

5

提示

制約

• $2\ <\ =\ N\ <\ =\ 500$
• $a_{ij}$ は . または # である。

部分点

• $300$ 点分のテストケースでは、$N\ <\ =\ 3$ が成り立つ。

Sample Explanation 1

例えば、次のように操作を行うと、次図のようにマス目の配色が変わります。 - $i\ =\ 1$, $j\ =\ 2$ と選んで操作を行う。 - $i\ =\ 1$, $j\ =\ 1$ と選んで操作を行う。 - $i\ =\ 1$, $j\ =\ 2$ と選んで操作を行う。