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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

 
 
public class Codeforces {
	
	static int mod=1000000007 ;
	static int dx[]= {1,1,1,0,-1,-1,-1,0};
	static int dy[]= {1,0,-1,-1,-1,0,1,1};
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		PrintWriter out=new PrintWriter(System.out);
	    FastScanner fs=new FastScanner();
	    int t=fs.nextInt();
	    
	    outer:while(t-->0) {
	    	int n=fs.nextInt();
	    	int a[]=new int[n];
	    	int b[]=new int[n];
	    	Map<Integer,List<Integer>> top=new HashMap<>();
	    	Map<Integer,Integer> dif=new HashMap<>();
	    	for(int i=0;i<n;i++) {
	    		a[i]=fs.nextInt();
	    		b[i]=fs.nextInt();
	    		if(!top.containsKey(a[i])) top.put(a[i],new ArrayList<>());
	    		
	    		top.get(a[i]).add(b[i]);
	    		
	    		dif.put(b[i], dif.getOrDefault(b[i], 0)+1);
	    	}
	    	long ans=nc3(n);
	    	long x=0,y=0,z=0;
	    	for(Map.Entry<Integer,List<Integer>> e:top.entrySet()) {
	    		long k=e.getKey();
	    		long v= e.getValue().size();
	    		for(int ele:e.getValue()) {
	    			ans-= (v-1)*(dif.get(ele)-1);
	    		}
//	    		x+= nc3(v);
//	    		y+= nc2(v)*(dif.size()-2);
	    		
	    	}
//	    	ans= nc3(top.size());
//	    	ans+= x+y;
	    	System.out.println(ans);
	    	
	    }
	    
		out.close();
	}
    static long nc2(long n) {
    	if(n<2) return 0;
    	return (n*(n-1))/2;
    }
    static long nc3(long n) {
    	if(n<3) return 0;
    	return (n*(n-1)*(n-2))/6;
    }
	static long pow(long a,long b) {
		if(b<0) return 1;
		long res=1;
		while(b!=0) {
			if((b&1)!=0) {
				res*=a;
				res%=mod;
			}
			a*=a;
			a%=mod;
			b=b>>1;
		}
		return res;
	}
	static long gcd(long  a,long  b) {
		if(b==0) return a;
		return gcd(b,a%b);
	}
	static long nck(int n,int k) {
		if(k>n) return 0;
		long res=1;
		res*=fact(n);
		res%=mod;
		res*=modInv(fact(k));
		res%=mod;
		res*=modInv(fact(n-k)); 
		res%=mod;
		return res;
	}
	static long fact(long n) {
//		return fact[(int)n];
		long res=1;
		for(int i=2;i<=n;i++) {
			res*=i;
			res%=mod;
		}
		return res;
	}
	
	static long modInv(long n) {
		return pow(n,mod-2);
	}
	
	static void sort(int[] a) {
		//suffle
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			int oi=r.nextInt(n);
			int temp=a[i];
			a[i]=a[oi];
			a[oi]=temp;
		}
		
		//then sort
		Arrays.sort(a);
	}
	
	// Use this to input code since it is faster than a Scanner
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		long[] lreadArray(int n) {
			long a[]=new long[n];
			for(int i=0;i<n;i++) a[i]=nextLong();
			return a;
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
 
}