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.
/**
 * check out my youtube channel sh0rkyboy
 * https://tinyurl.com/zdxe2y4z
 * I do screencasts, solutions, and other fun stuff in the future
 */

import java.util.*;
import java.io.*;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.Math.max;
public class EdC {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	public static MyScanner sc;
    public static PrintWriter out;
	public static void main(String[] largewang) throws Exception{
		// TODO Auto-generated method stub
 		sc = new MyScanner();
 		out = new PrintWriter(System.out);
 		int t = sc.nextInt();
 		while (t-->0) {
 			int n = sc.nextInt();
 			long[] freqCount = new long[n+1];
 			int[] b = new int[n+1];
 			int[] e = new int[n+1];
 			long[] arr1 = new long[n+1];
 			long[] arr2 = new long[n+1];
 			for(int j =0 ;j<n;j++){
 				int v1 = sc.nextInt();
 				int v2 = sc.nextInt();
 				b[j+1] = v1;
 				e[j+1] = v2;
 				arr1[v1]++;
 				arr2[v2]++;
 				freqCount[v1]++;
 				freqCount[v2]++;
 			}
// 			ArrayList<Long> arr = new ArrayList<>();
// 			for(int j = 1;j<=n;j++){
// 				if (arr1[j] > 0) {
// 					arr.add(arr1[j]);
// 				}
// 			}
// 			long[][] dp = new long[arr.size()+1][4];
// 			for(int j = 0;j<=arr.size();j++){
// 				dp[j][0] = 1;
// 			}
// 			dp[1][1] = arr.get(0);
// 			dp[2][2] = dp[1][1]*arr.get(1);
// 			dp[3][3] = dp[2][2]*arr.get(2);
// 			for(int j = 1;j<=arr.size();j++){
// 				for(int k = 1;k<=3;k++){
// 					if (j <=k)
// 						continue;
// 					dp[j][k] = arr.get(j-1)*dp[j-1][k-1] + dp[j-1][k];
// 				}
// 			}
// 			
// 			
// 			ArrayList<Long> arrN = new ArrayList<>();
// 			for(int j = 1;j<=n;j++){
// 				if (arr2[j] > 0) {
// 					arrN.add(arr2[j]);
// 				}
// 			}
// 			long[][] dp2 = new long[arr.size()+1][4];
// 			for(int j = 0;j<=arr.size();j++){
// 				dp2[j][0] = 1;
// 			}
// 			dp2[1][1] = arrN.get(0);
// 			dp2[2][2] = dp2[1][1]*arrN.get(1);
// 			dp2[3][3] = dp2[2][2]*arrN.get(2);
// 			for(int j = 1;j<=arrN.size();j++){
// 				for(int k = 1;k<=3;k++){
// 					if (j<=k)
// 						continue;
// 					dp2[j][k] = arrN.get(j-1)*dp2[j-1][k-1] + dp2[j-1][k];
// 				}
// 			}
 			
 			long ans = 0;
 			for (int j = 1;j<=n;j++){
 				ans -= (long)(arr1[(int)b[j]]-1)*(long)(arr2[(int)e[j]]-1);
 			}
 			ans += (long)n*(long)(n-1)*(long)(n-2)/6L;
 			out.println(ans);
 		}
 		out.close();
 		
 	}
	
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
	static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            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;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is