There is an $n \times n$ grid whose each square is initially white. On each move you can paint one row or column black.

Your task is to create a given target grid using the minimum number of moves.

Input

The first input line has an integer $n$: the size of the grid.

After this, there are $n$ lines of $n$ characters that describe the target grid. Each color is 0 (white) or 1 (black).

Output

Print the minimum number of moves needed. If the task is impossible, print $-1$.

Constraints

• $1 \le n \le 1000$

Example 1

Input:

3
001
111
001

Output:

2

Example 2

Input:

3
101
111
001

Output:

-1