Byteantean Towns

"A line segment is the shortest path between two points." This principle guided the road builders of the Byteantean Empire. Every road they built is a full straight line that runs across the whole country. Wherever two roads cross, the Byteanteans founded a town. To avoid ambiguity, they never let more than two roads pass through the same point.

The Emperor now wants to split the country into two provinces that are as balanced as possible in the number of towns. One existing road will serve as the border between the two provinces. Towns lying exactly on the border road belong to neither province and answer to the Emperor alone. For each road, the Emperor wants to know the absolute difference between the number of towns strictly on one side of that road and the number strictly on the other side.

Write a program that computes this value for every road.

The first line contains an integer $n$ ($1 \le n \le 1000$), the number of roads.

Each of the next $n$ lines contains four integers $x_1\ y_1\ x_2\ y_2$ ($-1000 \le x_1, y_1, x_2, y_2 \le 1000$), where $(x_1, y_1)$ and $(x_2, y_2)$ are two distinct points; the road is the straight line through them.

No two roads are identical, and no three roads meet at a single point. Every intersection of two roads lies inside the country.

Output $n$ lines. The $i$-th line contains one integer: for the $i$-th road (in input order), the absolute difference between the number of towns on one side of the road and the number of towns on the other side. Towns lying on the road itself are not counted.

In the sample, the four roads create five towns, at $(0, 0)$, $(1, 0)$, $(1, 1)$, $(2, 0)$, and $(2, 2)$.