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.
// package codeforces;

import java.io.*;
import java.util.*;

public class Contest_educational115_div2 {
	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	private static String next() throws IOException {

		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(br.readLine());
		}
		return st.nextToken();
	}

	static BufferedReader br;
	static StringTokenizer st;
	static BufferedWriter bw ;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t=nextInt();
		while(t-->0) {
			training_session();
		}
		bw.close();
	}
	
	public static void training_session()throws IOException {
		int n=nextInt();
		int[][]arr=new int[n][2];
		int[]t=new int[n];
		int[]d=new int[n];
		for(int i=0;i<n;i++) {
			arr[i][0]=nextInt();
			arr[i][1]=nextInt();
		}
		int[]a=new int[n+1];
		int[]b=new int[n+1];
		for(int[]x:arr) {
			a[x[0]]++;
			b[x[1]]++;
		}
		long ans=(long)(n)*(n-1)*(n-2)/6;
//		System.out.println(ans);
		for(int[]x:arr) {
			ans-=(long)(a[x[0]]-1)*((long)(b[x[1]])-1);
		}
		bw.append(ans+"\n");
		
		
	}
	
	public static void groups()throws IOException {
		int n=nextInt();
		int[][]arr=new int[n][5];
		for(int i=0;i<n;i++) {
			for(int j=0;j<5;j++) {
				arr[i][j]=nextInt();
			}
		}
		if(n%2!=0) {
			bw.append("NO"+"\n");
			return;
		}
		boolean bool=false;
		for(int i=0;i<5;i++) {
			for(int j=i+1;j<5;j++) {
				int a=0,b=0,c=0;
				for(int k=0;k<n;k++) {
					if(arr[k][i]==1 && arr[k][j]==1) {
						c++;
					}else if(arr[k][i]==1) {
						a++;
					}else if(arr[k][j]==1) {
						b++;
					}
				}
				if(a+b+c==n && a<=n/2 && b<=n/2) {
					bool=true;
				}
			}
		}
		if(bool) {
			bw.append("YES"+"\n");
		}else {
			bw.append("NO"+"\n");
		}
		
	}
	
	public static void delete_two_elements()throws IOException {
		double n=Double.parseDouble(next());
		double[]arr=new double[(int)n];
		double sum=0;
		HashMap<Double,Integer> map=new HashMap<>();
		for(int i=0;i<n;i++) {
			arr[i]=Double.parseDouble(next());
			map.put(arr[i],map.getOrDefault(arr[i],0)+1);
			sum+=arr[i];
		}
		double m=sum/n;
		double esum=m*(n-2);
		double diff=sum-esum;
		long ans=0;
		for(int i=0;i<n;i++) {
			if(arr[i]<=diff) {
				double v=diff-arr[i];
				if(!map.isEmpty() && map.containsKey(v)) {
					if(arr[i]==v && map.get(v)==1) {
						continue;
					}
					ans+=map.get(v);
					if(arr[i]==v) {
						ans--;
					}
				}
				
			}
		}
		ans=ans/2;
		bw.append(ans+"\n");
	}
	
	public static void computer_game() throws IOException{
		int n=nextInt();
		int[][]arr=new int[2][n];
		String str1=next();
		String str2=next();
		for(int i=0;i<n;i++) {
			arr[0][i]=str1.charAt(i)-'0';
		}
		for(int i=0;i<n;i++) {
			arr[1][i]=str2.charAt(i)-'0';
		}
		boolean b=true;
		for(int i=0;i<n;i++) {
			if(arr[0][i]==1 && arr[1][i]==1) {
				b=false;
				break;
			}
		}
		if(b && arr[0][0]!=1 && arr[1][n-1]!=1) {
			bw.append("YES\n");
		}else {
			bw.append("NO\n");
		}
		
	}

	
}




