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.

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// MACROS
#define int                     long long
#define pb                      push_back
#define MAX                     2e18+5
#define MIN                     -2e18-5
#define mod                     1000000007
#define eps                     1e-9
#define set(x)                  memset(x, 0, sizeof(x))
#define clr(x)                  memset(x, -1, sizeof(x))
#define ff                      first
#define ss                      second
#define rep(i,a,b)              for(int i=a;i<b;i++)
#define sz(x)                   x.size()
#define endl                    "\n"
#define deb(x)                  cout << #x << "=" << x << endl
#define deb2(x, y)              cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z)           cout << #x << "=" << x << "," << #y << "=" << y<< "," << #z << "=" << z << endl
#define deb4(x, y, z, a)        cout << #x << "=" << x << "," << #y << "=" << y<< "," << #z << "=" << z << "," << #a << "=" << a << endl
#define all(x)                  x.begin(), x.end()

typedef priority_queue<int>     maxHeap;
typedef priority_queue<int,     vector<int>, greater<int>> minHeap;
typedef pair<int, int>          pii;
typedef vector<int>             vi;
typedef vector<pii>             vpii;
typedef map<int, int>            mpii;
typedef set<int>                seti;
template<typename T> // find_by_order, order_of_key
using pbds = tree<T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>;
template<typename T, typename T1>T amax(T &a, T1 b) {if (b > a)a = b; return a;}
template<typename T, typename T1>T amin(T &a, T1 b) {if (b < a)a = b; return a;}
// typedef long long int           ll;

int mpow(int base, int exp);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}


// cout << fixed << setprecision(9) <<
const int N = 3e5 + 5;
int n;
pii a[N];

int BIT[N + 10];

int query(int idx) {
    int ans = 0;
    for (; idx > 0; idx -= idx & (-idx)) {
        ans += BIT[idx];
    }
    return ans;
}

void update(int idx, int val) {
    for (; idx <= n; idx += idx & (-idx)) // You can change to N if u want
        BIT[idx] += val;
}
bool cmp(pii a, pii b) {
    if (a.ss == b.ss) return a.ff < b.ff;
    return a.ss < b.ss;
}

void solve() {
    cin >> n;
    seti tmp;
    for (int i = 0; i <= n + 1; i++) BIT[i] = 0;
    rep(i, 0, n) {cin >> a[i].ff >> a[i].ss; tmp.insert(a[i].ss);}
    int ans = 0;
    sort(a, a + n, cmp);
    map<int, vi> mp;
    for (int i = 0; i < n; i++) {
        mp[a[i].ff].pb(a[i].ss);
    }
    for (auto &i : mp) {
        sort(all(i.ss));
    }
    rep(i, 0, n) update(a[i].ff, 1);
    for (int i = 0; i < n; i++) {
        int l = query(a[i].ff - 1);
        int r = query(n) - query(a[i].ff);
        // deb3(i, l, r);
        ans += l * r;

    }
    // deb(ans);
    int cur = 0;
    for (auto i : mp) {
        vi &v = i.ss;
        int sz = v.size();
        mpii cnt;
        seti s;
        for (int j = 0; j < sz; j++) {
            auto lb = lower_bound(all(v), v[j]) - v.begin();
            auto ub = upper_bound(all(v), v[j]) - v.begin();
            // deb4(i.ff, v[j], lb, ub);
            ans += lb * (sz - ub);
            s.insert(v[j]);
        }
        // deb(ans);
        for (int i : s) tmp.erase(i);
        if (s.size() >= 2)
            ans += (((s.size() - 1) * s.size()) / 2) * tmp.size();
        for (int i : s) tmp.insert(i);
        // deb(ans);

    }
    cout << ans << endl;

}


/* TIPS
1. for interactive prob remove fastio and endl
2. for vector pass as reference
3. dont use set and clr when n * t is very large use loop till n instead.
4. don't forget to clear the graph
5.

*/



int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {

        // cout<<"Case #"<<i<<": ";

        solve();


    }
    return 0;
}

int mpow(int base, int exp) {
    base %= mod;
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = ((int)result * base) % mod;
        base = ((int)base * base) % mod;
        exp >>= 1;
    }
    return result;
}

