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