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.
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>-

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

// template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define show(a) cerr << #a <<" -> "<< a <<" "
#define nl cerr <<"\n"
#define int ll

const int N = 2e5 + 5;
const int oo = 1e9 + 5;

ll all_pairs(ll sz) {
    return (sz * (sz - 1)) / 2;
}

int n, a[N], b[N], cntA[N], cntB[N], cntAA[N], cntBB[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        ++cntA[a[i]];
        ++cntB[b[i]];
    }
    for (int i = n; i >= 1; --i) {
        cntAA[a[i]] = --cntA[a[i]];
        cntBB[b[i]] = --cntB[b[i]];
    }
    for (int i = 1; i <= n; ++i) {
        ++cntA[a[i]];
        ++cntB[b[i]];
    }
    ll ans = 0ll;
    for (int i = 1; i <= n; ++i) {
        --cntA[a[i]];
        --cntB[b[i]];
        ans += all_pairs(n - i - cntA[a[i]]);
        ans += all_pairs(n - i - cntB[b[i]]);
        ans -= all_pairs(n - i - cntA[a[i]] - cntB[b[i]]);
        ans -= (i - 1 - cntAA[a[i]]) * cntA[a[i]];
        ans -= (i - 1 - cntBB[b[i]]) * cntB[b[i]];
    }
    cout << ans <<"\n";
}

 main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tests = 1;
	cin >> tests;
	while (tests --) {
		solve();
	}
	return 0;
}
/*
    Just Chalish!
*/
