#include <bits/stdc++.h>
using namespace std;
const int mxn = 200000, m = 3;
long long n, k;
long long a[mxn][2], b[mxn], d[mxn], h[mxn], dp[2][m + 1];
vector<int> v[mxn][2];
map<int, vector<int>> first[mxn];
void answer() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    first[i].clear();
    for (int j = 0; j < 2; j++) v[i][j].clear();
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> a[i][j];
      v[--a[i][j]][j].push_back(i);
    }
    first[a[i][0]][a[i][1]].push_back(i);
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = dp[1][0] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
      for (int l = m; l; l--) {
        dp[j][l] += v[i][j].size() * dp[j][l - 1];
      }
  k = 0;
  for (int i = 0; i < n; i++) {
    b[i] = n + first[a[i][0]][a[i][1]].size(), d[i] = 1;
    for (int j = 0; j < 2; j++) b[i] -= v[a[i][j]][j].size();
    k += b[i];
  }
  k /= 2;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++) {
      for (int l : v[i][j]) h[a[l][!j]]++;
      for (int l : v[i][j]) d[l] *= v[i][j].size() - h[a[l][!j]];
      for (int l : v[i][j]) h[a[l][!j]]--;
    }
  for (int i = 0; i < n; i++)
    for (auto j : first[i]) {
      long long x = 0;
      for (int l : j.second) x += b[l];
      for (int l : j.second) d[l] += k + x;
    }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++) {
      long long x = 0;
      for (int l : v[i][j]) x += b[l];
      for (int l : v[i][j]) d[l] -= x;
    }
  long long ret = dp[0][m] + dp[1][m], x = 0;
  for (int i = 0; i < n; i++) x += d[i];
  ret -= x / 3;
  cout << ret << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) answer();
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 a_i (an integer from 1 to n) and a difficulty b_i (an integer from 1 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 3 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 ≤ t ≤ 50000) — the number of testcases.

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

In the i-th of the following n lines, there are two integers a_i and b_i (1 ≤ a_i, b_i ≤ 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 ⋅ 10^5.

Output

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

Example

Input


2
4
2 4
3 4
2 1
1 3
5
1 5
2 4
3 3
4 2
5 1


Output


3
10

Note

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

  * problems 1, 2, 4; 
  * problems 1, 3, 4; 
  * problems 2, 3, 4. 



Thus, the number of ways is equal to three.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mxn = 200000, m = 3;
long long n, k;
long long a[mxn][2], b[mxn], d[mxn], h[mxn], dp[2][m + 1];
vector<int> v[mxn][2];
map<int, vector<int>> first[mxn];
void answer() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    first[i].clear();
    for (int j = 0; j < 2; j++) v[i][j].clear();
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> a[i][j];
      v[--a[i][j]][j].push_back(i);
    }
    first[a[i][0]][a[i][1]].push_back(i);
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = dp[1][0] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
      for (int l = m; l; l--) {
        dp[j][l] += v[i][j].size() * dp[j][l - 1];
      }
  k = 0;
  for (int i = 0; i < n; i++) {
    b[i] = n + first[a[i][0]][a[i][1]].size(), d[i] = 1;
    for (int j = 0; j < 2; j++) b[i] -= v[a[i][j]][j].size();
    k += b[i];
  }
  k /= 2;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++) {
      for (int l : v[i][j]) h[a[l][!j]]++;
      for (int l : v[i][j]) d[l] *= v[i][j].size() - h[a[l][!j]];
      for (int l : v[i][j]) h[a[l][!j]]--;
    }
  for (int i = 0; i < n; i++)
    for (auto j : first[i]) {
      long long x = 0;
      for (int l : j.second) x += b[l];
      for (int l : j.second) d[l] += k + x;
    }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++) {
      long long x = 0;
      for (int l : v[i][j]) x += b[l];
      for (int l : v[i][j]) d[l] -= x;
    }
  long long ret = dp[0][m] + dp[1][m], x = 0;
  for (int i = 0; i < n; i++) x += d[i];
  ret -= x / 3;
  cout << ret << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) answer();
  return 0;
}

```