Problem1029--Tin Cutter II

1029: Tin Cutter II

[Creator : ]
Time Limit : 3.000 sec  Memory Limit : 128 MB

Submit

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 length of visible border lines at the end of the given sequence of cuts. Write a program that answers this question.
Here are four examples:

The first row in the picture are four cuttings and the second row are their corresponding resulting plates. Each gray area is a separate hole, and thick lines are visible border lines after cutting. There are 2, 2, 1, 1 holes respectively (from left to right), and the length of visible border lines are 8, 26, 12, 20 respectively.

Input

The first line of input contains a single integer T (T<=100), the number of test cases. The first line of each test case contains an integer n (1<=n<=100), the number of segment cuts. Each of the following n lines describe a segment cut with four integers x1, y1, x2, y2 that means a segment cut from (x1,y1) to (x2,y2) (0<=x1,y1,x2,y2<=10000). The segment is always horizontal or vertical.

Output

For each test case, print the total length of the border lines.

Sample Input Copy

4
6
0 0 1 0
1 0 1 2
1 2 2 2
2 2 2 1
2 1 0 1
0 1 0 0
9
0 0 4 0
4 0 4 4
4 4 0 4
0 4 0 0
6 1 8 1
8 1 8 3
8 3 6 3
6 3 6 1
2 2 7 2
8
0 1 3 1
3 1 3 2
3 2 0 2
0 2 0 1
1 0 2 0
2 0 2 3
2 3 1 3
1 3 1 0
8
0 1 4 1
4 1 4 4
4 4 0 4
0 4 0 1
3 0 6 0
6 0 6 2
6 2 3 2
3 2 3 0

Sample Output Copy

8
26
12
20