1091 - Tin Cutter

Time limit : 3 sMemory limit : 32 mb
Submitted : 81Accepted : 50

Problem Description

In a Tin Cutting factory there is a machine for cutting parts from tin plates. It has an extraordinarily sharp knife able to make horizontal or vertical segment cuts in the tin plates. Each cutting process consists of a sequence of such cuts. Each segment cut is given by its endpoints that are always located inside the tin plate. During the cutting process some parts of tin plate can fall out and so some holes in the plate can emerge.

Factory management needs to predict the number of holes in the plate at the end of the given sequence of cuts. Write a program that answers this question. Single segment cuts are not considered to be holes.

Here there are examples of some situations that can arise after cutting:

"""

two holes two holes one hole one hole

Input

The last block consists of just one line containing 0.

Output

There is no line in the output corresponding to the last null'' block of the input.

4
0 1 1 1
1 1 1 0
1 0 0 0
0 0 0 1
2
0 1 2 1
1 2 1 0
0

1
0