Training Session solution codeforces

Training Session solution codeforces

Monocarp is the coach of the Berland State University programming teams. He decided to compose a problemset for a training session for his teams.

Monocarp has 𝑛n problems that none of his students have seen yet. The 𝑖i-th problem has a topic 𝑎𝑖ai (an integer from 11 to 𝑛n) and a difficulty 𝑏𝑖bi (an integer from 11 to 𝑛n). All problems are different, that is, there are no two tasks that have the same topic and difficulty at the same time.

Monocarp decided to select exactly 33 problems from 𝑛n problems for the problemset. The problems should satisfy at least one of two conditions (possibly, both):

  • the topics of all three selected problems are different;
  • the difficulties of all three selected problems are different.

Your task is to determine the number of ways to select three problems for the problemset.

Input

The first line contains a single integer 𝑡t (1≤𝑡≤500001≤t≤50000) — the number of testcases.

The first line of each testcase contains an integer 𝑛n (3≤𝑛≤2⋅1053≤n≤2⋅105) — the number of problems that Monocarp have.

In the 𝑖i-th of the following 𝑛n lines, there are two integers 𝑎𝑖ai and 𝑏𝑖bi (1≤𝑎𝑖,𝑏𝑖≤𝑛1≤ai,bi≤n) — the topic and the difficulty of the 𝑖i-th problem.

It is guaranteed that there are no two problems that have the same topic and difficulty at the same time.

The sum of 𝑛n over all testcases doesn’t exceed 2⋅1052⋅105.

Output

Print the number of ways to select three training problems that meet either of the requirements described in the statement.

Example
input

Copy
2
4
2 4
3 4
2 1
1 3
5
1 5
2 4
3 3
4 2
5 1
output

Copy
3
10
Note

In the first example, you can take the following sets of three problems:

  • problems 11, 22, 44;
  • problems 11, 33, 44;
  • problems 22, 33, 44.

Thus, the number of ways is equal to three.

Leave a Comment