Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3400
Treasure Hunting

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Suffered from the economic crisis, the government has a great deficit, so they decide to exploit a treasure area.

In this area, each lattice point has one unit of treasure, and the government plans to build up N tunnels, which will start from one lattice point and end at another lattice point. As the tunnel pass a lattice point, that unit of treasure will be obtained by the government. Unfortunately, because of the poor plan, the tunnels may overlap or intersect with each other. However, even if multiple tunnels intersect at a grid point, the government can get only 1 unit of treasure at each of these intersections.

According to the plan, the government wants to know how much treasure they can get in advance.


There're multiple test cases (no more than 20).

The first line of each test case contains an integer N (1 <= N <= 1000), indicating the number of tunnels.

The following N lines contain four integer x1, y1, x2 and y2(|x1 - x2| + |y1 - y2| > 0), represents the starting and ending points of the ith tunnel. The absolute value of x1, y1, x2 and y2 will no larger than 1000000.


Output the quantity of the treasure the government will get.

Sample Input

0 0 2 4
0 0 4 2
2 0 2 4
3 0 0 3
2 4 5 5
4 2 5 5

Sample Output



The chart of the sample:

Author: OUYANG,Jialin
Contest: ZOJ Monthly, September 2010
Submit    Status