This page is still under construction.

Parts of this page are still being built. What you see may change.

Northwest Wind

Time limit1sMemory limit256 MB

Summary
Count pairs of islands where one can sail to the other moving only east or south (both coordinates monotone between the two points).
Level

Medium5 of 10

Topics
Sorting, Prefix sum, Binary search, Array
Solved
No attempts yet

Problem

A strong northwest wind is blowing. This means you can sail in any direction between east and south (including due east and due south), but you can never sail toward the north or the west.

There is a sea dotted with several small islands. Each island is a point in the coordinate plane, where increasing yy points north and increasing xx points east.

A pair of islands counts if you can sail from one of them to the other using the northwest wind. Write a program that counts the number of island pairs you can travel between with the northwest wind.

Input

The first line contains the number of test cases TT.

The first line of each test case contains the number of islands nn (1≤n≤75 0001 \le n \le 75\,000). Each of the next nn lines contains the coordinates xix_i and yiy_i of one island, separated by a space (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9). No two islands share the same coordinates.

Output

For each test case, print the number of island pairs you can travel between with the northwest wind, one per line.

Examples1

  1. Example 1

    Input
    2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1
    Expected output
    5
3