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 Main {
		static long mod = 1000000007;
		static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		public static void main(String[] args) throws IOException  {
			FastReader sc = new FastReader();
			int t = sc.nextInt();
			while( t-- > 0) {
				long n = sc.nextLong();
				HashMap<Long,Long> fst= new HashMap<>();
				HashMap<Long,Long> scnd = new HashMap<>();
				long x[] = new long[(int)n];
				long y[] = new long[(int)n];
				for( int i = 0 ;i < n ;i++) {
					long a = sc.nextLong();
					long b = sc.nextLong();
					x[i] = a;
					y[i] = b;
					if( !fst.containsKey(a)) {
						fst.put( a, 1L);
					}
					else {
						fst.put(a, fst.get(a)+1);
					}
					if( !scnd.containsKey(b)) {
						scnd.put(b, 1L);
					}
					else {
						scnd.put(b, scnd.get(b)+1);
					}
				}
				long sum = (n)*(n-2)*(n-1)/6L;
			//	out.println("sum " + sum);
				long temp = 0;
				for( int i = 0 ;i < n;i++) {
					if( fst.get(x[i]) > 1) {
				//		out.println( x[i] +" " + y[i]);
						temp+=(fst.get(x[i]) -1)*(scnd.get(y[i]) - 1);
		//				out.println(temp);
					}
				}
				out.println(sum - temp);
			}
			out.flush();
		}
		
		public static boolean ifpowof2(long n ) {
			return ((n&(n-1)) == 0);
		}
		
		public static int[] nextLargerElement(int[] arr, int n)	{ 
			Stack<Integer> stack = new Stack<>();
			int rtrn[] = new int[n];
			rtrn[n-1] = -1;
	        stack.push( n-1);
	        for( int i = n-2 ;i >= 0 ; i--){
	            int temp = arr[i];
	            int lol = -1;
	            while( !stack.isEmpty() && arr[stack.peek()] <= temp){
	            	if(arr[stack.peek()] == temp ) {
	            		lol = stack.peek();
	            	}
	                stack.pop();
	            }
	            if( stack.isEmpty()){
	            	if( lol != -1) {
	            		rtrn[i] = lol;
	            	}
	            	else {
	            		rtrn[i] = -1;
	            	}
	            }
	            else{
	            	rtrn[i] = stack.peek();
	            }
	            stack.push( i);
	        }
	        return rtrn;
		}
		
		static int gcd(int a, int b)
		{
			if (a == 0)
				return b;
			return gcd(b % a, a);
		}
		
			   
		 static int lcm(int a, int b)
		 {
			 return (a / gcd(a, b)) * b;
		 }
		 

		 static long rightmostsetbit(long n) {
			 return n&-n;
		 }
		 
		 static long leftmostsetbit(long n)
		    {
		        long k = (long)(Math.log(n) / Math.log(2));
		        return 1 << k;
		    }
	 
		 static HashMap<Long,Long> primefactor( long n){
			 HashMap<Long ,Long> hm = new HashMap<>();
			 long temp = 0;
			 while( n%2 == 0) {
				 temp++;
				 n/=2;
			 }	
			 if( temp!= 0) {
				 hm.put( 2L, temp);
			 }
			 long c = (long)Math.sqrt(n);
			 for( long i = 3 ; i <= c ; i+=2) {
				 temp = 0;
				 while( n% i == 0) {
					 temp++;
					 n/=i;
				 }
				 if( temp!= 0) {
					 hm.put( i, temp);
				 }
	 		 }
	 		 if( n!= 1) {
	 			 hm.put( n , 1L);
	 		 }
	 		 return hm;	
		 }
	 
		 static class FastReader {
			 BufferedReader br;
			 StringTokenizer st;
		 
			 public FastReader()
			 {
				 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;
			 }
		 }	
}