제출: 21 통과: 11

[제출] [채점기록] [묻고답하기]

A strong North-Western wind is blowing. When sailing this means that you can sail to the East, to the South or to any direction between East and South. It is impossible to go either North- or Westwards.

In the ocean there are a large number of small islands. These islands are described by coordinate pairs (x, y) on a grid. The positive y-direction is Northwards and the positive x-direction is Eastwards. We’d like to sail from one island to another. For how many pairs of islands is this possible? (Note: a pair consists of two diﬀerent islands.)

The ﬁrst line of the input ﬁle contains a single number: the number of test cases to follow. Each test case has the following format:

- One line with one number n with 1 ≤ n ≤ 75,000: the number of islands.
- n lines with two numbers xi and yi with −1,000,000,000 ≤ xi, yi ≤ 1,000,000,000: the coordinates of the islands. No two islands are located at the same coordinates.

For every test case in the input ﬁle, the output should contain a single number, on a single line: the number of pairs of islands for which you can sail from one to the other.

```
2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1
```

```
5
3
```