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.
import sys
input = sys.stdin.readline
from collections import Counter
def il(): #Input list
    return list(map(int,input().split()))
def ii(): #Input int
    return int(input())
def imi(): #Input multiple int
    return map(int,input().split())
def ist(): #Input String
    return input()

T=ii()
for _ in range(T):
    n=ii()
    li=[]

    t=Counter([])
    d=Counter([])

    for i in range(n):
        a,b=imi()
        t[a]+=1
        d[b]+=1
        li.append((a,b))
    pt=[0]*(n+1)
    pd=[0]*(n+1)
    s=0
    sd=0
    for i in range(n,1,-1):
        s+=t[i]
        sd+=d[i]
        pt[i-1]=t[i-1]*s
        pd[i-1]=d[i-1]*sd
    s=0
    sd=0
    A=0
    B=0
    for i in range(n,1,-1):
        s+=pt[i]
        sd+=pd[i]
        A+=t[i-1]*s
        B+=d[i-1]*sd

   # print(d,pd)


    aib=0
    N=n
    for e in li:
        a,b=e
        aib+= (t[a]-1)*(N-t[a]) + (t[a]-1)*max(0,t[a]-2) + (d[b]-1)*max((N-t[a]-d[b]+1),0) + (d[b]-1)*max(0,d[b]-2)
        t[a]-=1
        d[b]-=1
        N-=1

    aib= (n*(n-1)*(n-2))//6 - aib

    #print(A,B,aib)

    print(A+B-aib)



