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.
#!/usr/bin/env python
from __future__ import division, print_function
from collections import defaultdict, deque
import heapq
import os
import copy 
import sys
from io import BytesIO, IOBase
from typing import Counter, DefaultDict, Deque, OrderedDict
import bisect, math, time

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
from math import ceil, log2
MOD = 1000000007
def power(x,y):
    if y == 0:
        return 1
    if x == 0:
        return 0
    temp = power(x, y//2)
    if (y % 2 == 0):
        return temp * temp % MOD
    else:
        return x * temp * temp % MOD
def RightAngled(a, n):
     
    # To store the number of points
    # has same x or y coordinates
    xpoints = defaultdict(lambda:0)
    ypoints = defaultdict(lambda:0)
     
    for i in range(n):
        xpoints[a[i][0]] += 1
        ypoints[a[i][1]] += 1
         
    # Store the total count of triangle
    count = 0
     
    # Iterate to check for total number
    # of possible triangle
    for i in range(n):
        if (xpoints[a[i][0]] >= 1 and
            ypoints[a[i][1]] >= 1):
             
            # Add the count of triangles
            # formed
            count += ((xpoints[a[i][0]] - 1) *
                      (ypoints[a[i][1]] - 1))
             
    # Total possible triangle
    return count

def main():
    t = int(input())
    while t:
        n = int(input())
        points = []
        for _ in range(n):
            x,y = map(int, input().split())
            points.append([x,y])
        ncr = (n*(n-1)*(n-2))//(3*2)
        cnt = RightAngled(points, n)
        
        
        
        print((ncr - cnt))
        t -= 1
                

# 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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()
