Partitions

Time Limit: 10 Seconds    Memory Limit: 1024 KB

Given a maze, you are to tell the number of partitions in it.

Input

The first line is an integer N (2 <= N <= 3000), the size of the maze.

The next N lines each has N 0-and-1's, 1 for an obstacle and 0 for an unoccupied space.

Two unoccupied spaces are in the same partition if:

1. They are adjacent (above, below, left/right to,but not diagonally), or

2. They are both connected with another unoccupied space.

Output

One number on a line - the number of partitions.

Sample Input

2
0 1
1 0

Sample Output

2

Submit

Source: ZOJ Monthly, January 2003