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.
# template begins
#####################################
from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_right
from cffi import FFI
from time import perf_counter


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
def mint(): return map(int, input().split())
def mfloat(): return map(float, input().split())
def intin(): return int(input())


def make_nCr_mod(max_n=2 * 10**5, mod=10**9 + 7):
    max_n = min(max_n, mod - 1)

    fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
    fact[0] = 1
    for i in range(max_n):
        fact[i + 1] = fact[i] * (i + 1) % mod

    inv_fact[-1] = pow(fact[-1], mod - 2, mod)
    for i in reversed(range(max_n)):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

    def nCr_mod(n, r):
        res = 1
        while n or r:
            a, b = n % mod, r % mod
            if a < b:
                return 0
            res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
            n //= mod
            r //= mod
        return res

    return nCr_mod
#####################################
# template ends
# Use the recursion snippet if heavy recursion is needed (depth>1000)
# If constraints are tight, use 1d arrays instead of 2d, like g[i*m+j] instead of g[i][j]


def summation(n):
    return n*(n+1)//2


def solve(nCr):
    n = int(input())
    problems = [list(mint()) for i in range(n)]
    sames = {i: [] for i, j in problems}
    for i, j in problems:
        sames[i].append(j)
    # print(sames)
    for key, value in sames.items():
        d = {}
        for i in value:
            d[i] = d.get(i, 0) + 1
        sames[key] = d
    # print(sames)
    distinct_groups = len(sames)
    # print(distinct_groups)
    base_answer = nCr(distinct_groups, 3) + ((summation(distinct_groups-2))*(n-distinct_groups))
    # print(base_answer)
    total_freq = {}
    band_wise = {}
    for i, j in problems:
        total_freq[j] = total_freq.get(j, 0) + 1
        band_wise[(i, j)] = band_wise.get((i, j), 0) + 1
    for key, value in sames.items():
        # print(key, value)
        s = sum(value.values())
        l = len(value)
        base_answer += nCr(l, 3) + ((summation(l-2))*(s-l))
        base_answer += (n-s)*(nCr(l, 2) + (l-1)*(s-l))
        for k, v in value.items():
            outside = total_freq[k]-band_wise.get((key, k), 0)
            # if outside == 1:
            #     print(f"l={l}, v={v}")
            base_answer -= outside * (l-1+v-1)
        # print(f"After {key}, base_value={base_answer}")

    print(base_answer)

    """
    if all i had the same j, answer would be
    (distinct i) choose (3) * (sum of lengths 3 chosen groups)
    if there are n groups, ans = (n choose 3) + ((summation(n-2)) * (sum_of_lengths-n))
    """
    # from itertools import combinations
    # m = 8
    # l = list(combinations(range(1, m), 3))
    # d = {}
    # for i in range(1, m):
    #     d[i] = sum(x.count(i) for x in l)
    # print(d)


def main():
    t = 1
    t = int(input())
    nCr = make_nCr_mod()
    for _ in range(t):
        solve(nCr)


if __name__ == "__main__":
    start_time = perf_counter()
    main()
    print(perf_counter()-start_time, file=sys.stderr)
