Counting Rectangles

Interview

Time limit1sMemory limit128 MB

Summary

Count rectangles whose four corners are all intersection points of horizontal and vertical segments in a figure.

Level: Medium6 of 10
Topics: Geometry, Hash map, Brute force, Implementation
Solved: No attempts yet

Problem

You are given a figure made up of only horizontal and vertical line segments. Your goal is to count how many distinct rectangles are formed by these segments. For example, the two figures below contain 5 and 0 rectangles respectively.

The figure contains many intersection points. An intersection point is a point shared by two or more segments. The input segments are guaranteed to be arranged so that every intersection point is formed by exactly one horizontal segment meeting exactly one vertical segment.

A rectangle is bounded by two distinct horizontal segments and two distinct vertical segments, and all four of its corners must be intersection points.

Input

The first line contains a single integer $M$ , the number of test cases ( $1 \le M \le 10$ ). The data for the test cases follows. Each test case begins with a line containing $s$ , the number of segments in the figure ( $1 \le s \le 100$ ). The next $s$ lines each contain four integers $x_1\ y_1\ x_2\ y_2$ , the $x$ and $y$ coordinates of the two endpoints of one segment. All coordinates are integers between $0$ and $1000$ , and every segment is either horizontal or vertical.

Output

For each test case, print the number of distinct rectangles in its figure. Print the answer for each test case on its own line.

Examples1

Example 1

Input

2
6
0 0 0 20
0 10 25 10
20 10 20 20
0 0 10 0
10 0 10 20
0 20 20 20
3
5 0 5 20
15 5 15 25
0 10 25 10

Expected output

5
0