human
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.
Solve the task in PYTHON3.
assistant
#Here is Python code to determine the number of ways to select three problems for the problemset.

def main():
    alpha = 'abcdefghijklmnopqrstuvwxyz'
    ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    inf = 1e17
    mod = 10 ** 9 + 7

    # Max = 10 ** 6
    # primes = []
    # prime = [True for i in range(Max + 1)]
    # p = 2
    # while (p * p <= Max + 1):
    #
    #     # If prime[p] is not
    #     # changed, then it is a prime
    #     if (prime[p] == True):
    #
    #         # Update all multiples of p
    #         for i in range(p * p, Max + 1, p):
    #             prime[i] = False
    #     p += 1
    #
    # for p in range(2, Max + 1):
    #     if prime[p]:
    #         primes.append(p)

    #print(len(primes))

    def factorial(n):
        f = 1

        for i in range(1, n + 1):
            f = (f * i) % mod  # Now f never can
        # exceed 10^9+7

        return f

    def ncr(n, r):
        # initialize numerator
        # and denominator
        num = den = 1
        for i in range(r):
            num = (num * (n - i)) % mod
            den = (den * (i + 1)) % mod
        return (num * pow(den,
                          mod - 2, mod)) % mod



    def solve(n,a,b):

        atob = dict()

        btoa = dict()

        for i in range(n):

            if a[i] in atob:
                atob[a[i]].add(b[i])
            else:
                atob[a[i]] = {b[i]}

            if b[i] in btoa:
                btoa[b[i]].add(a[i])
            else:
                btoa[b[i]] = {a[i]}

        #print(atob)
        #print(btoa)

        cnt = 0
        for ele in atob:

            for x in atob[ele]:

                cnt += (len(btoa[x])-1)*(len(atob[ele])-1)

        return (n*(n-1)*(n-2))//6 - cnt






    t = int(input())
    ans = []
    for _ in range(t):
        n = int(input())

        #n,m = map(int, input().split())
        #r1 = list(input()[:-1])
        #r2 = list(input()[:-1])

        a = []
        b = []

        for i in range(n):
            s = [int(x) for x in input().split()]
            a.append(s[0])
            b.append(s[1])

        #a = [int(x) for x in...