Rope Intranet

A company occupies two very tall buildings. The intranet that connects the buildings is made of many cables, and each cable joins one window of the first building to one window of the second building.

You look at the buildings from the side, so one building is on the left and the other is on the right. The windows of the left building appear as points on its right wall, and the windows of the right building appear as points on its left wall. A cable is a straight segment from a window of the left building to a window of the right building.

No two cables share a window, so at most one cable leaves any window. From where you stand, however, some cables cross each other partway. Exactly two cables meet at every intersection point.

In the picture above, the black circles are the intersection points and the white circles are the windows.

How many intersection points do you see?

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains the number of cables you see, $N$.

Each of the next $N$ lines describes one cable with two integers $A_i$ and $B_i$, the windows that this cable joins. $A_i$ is the height of the window on the left building, and $B_i$ is the height of the window on the right building.

Limits

• $1 \le T \le 15$
• $1 \le N \le 1\,000$
• $1 \le A_i \le 10^4$
• $1 \le B_i \le 10^4$
• Within one test case, all $A_i$ are different.
• Within one test case, all $B_i$ are different.
• No three cables meet at the same point.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of intersection points you see.