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 java.util.*;
import java.io.*;
 
public  class SolutionD{
       public static void main(String[] args) throws Exception{
               Fast sc=new Fast();
        PrintWriter out=new PrintWriter(System.out);
             

             int t=sc.nextInt();
             while(t-->0){
             int n=sc.nextInt();
            int[] ar=new int[n];
            int[] br=new int[n];
            int[] fre=new int[n+1];
            int[] cnt=new int[n+1];
            for(int i=0;i<n;i++){
              ar[i]=sc.nextInt();
              br[i]=sc.nextInt();
              fre[ar[i]]++;
              cnt[br[i]]++;
            }

            long ans=0;
            long a=0;
            long b=0;
            for(int i=1;i<=n;i++){
              if(fre[i]>0)a++;
              if(cnt[i]>0)b++;
            }
            long val=0;
            long val2=0;
            if(a>=(long)3){
              
                 for(long i=a;i>=2;i--){
                     long v=(i-2);
                     val+=(v*(v+(long)1))/(long)2;
                 }
                 ans+=val;
            }
            if(b>=(long)3){
                 for(long i=b;i>=2;i--){
                     long v=(i-2);
                     val2+=(v*(v+(long)1))/(long)2;
                 }
                 ans+=val2;
            }
            ans+=Math.min(val2,val);
            long tot=0;
            for(long i=n;i>=2;i--){
                     long v=(i-2);
                     tot+=(v*(v+(long)1))/(long)2;
                 }
                 

            out.println(Math.min(ans,tot));
          }


             
        out.close();  
  }


static void Sort(int[] ar){
    ArrayList<Integer> al=new ArrayList<>();
    for(int i=0;i<ar.length;i++){al.add(ar[i]);}
    Collections.sort(al);
    for(int i=0;i<al.size();i++)ar[i]=al.get(i);
  }
static int gcd(int a,int b){
    if(b==0) return a;
    else return  gcd(b,a%b);
}
}
class Pair{
    int x, y;
     Pair(int x,int y){
        this.x=x;
        this.y=y;
     }
}
class Fast{
  BufferedReader br; 
  StringTokenizer st;
  public Fast(){ br=new BufferedReader(new InputStreamReader(System.in)); }
  String next() 
        {  while (st == null || !st.hasMoreElements()) 
            {   try
                {     st = new StringTokenizer(br.readLine()); } 
                catch (IOException  e) 
                {    e.printStackTrace(); } 
            } 
            return st.nextToken(); 
        }
  int nextInt(){  return Integer.parseInt(next()); }
  long nextLong(){     return Long.parseLong(next()); } 
  double nextDouble() {     return Double.parseDouble(next()); } 
  String nextLine() 
        { 
            String str = ""; 
            try{      str = br.readLine(); } 
            catch (IOException e)  {  e.printStackTrace(); } 
            return str; 
        } 
}
    