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.*;
import java.util.*;

public class Training{
    //--------------------------INPUT READER--------------------------------//
    static class fs {
        public BufferedReader br;
        StringTokenizer st = new StringTokenizer("");

        public fs() { this(System.in); }
        public fs(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        String next() {
            while (!st.hasMoreTokens()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }

        int ni() { return Integer.parseInt(next()); }
        long nl() { return Long.parseLong(next()); }
        double nd() { return Double.parseDouble(next()); }
        String ns() { return next(); }

        int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

        long[] nal(int n) {
            long[] l = new long[n];
            for(int i = 0; i < n; i++) l[i] = nl();
            return l;
        }
    }
    //-----------------------------------------------------------------------//

    //---------------------------PRINTER-------------------------------------//
    static class Printer {
        static PrintWriter w;
        public Printer() {this(System.out);}
        public Printer(OutputStream os) {
            w = new PrintWriter(os);
        }
        public void p(int i) {w.println(i);};
        public void p(long l) {w.println(l);};
        public void p(double d) {w.println(d);};
        public void p(String s) { w.println(s);};
        public void pr(int i) {w.println(i);};
        public void pr(long l) {w.print(l);};
        public void pr(double d) {w.print(d);};
        public void pr(String s) { w.print(s);};
        public void pl() {w.println();};
        public void close() {w.close();};
    }
    //------------------------------------------------------------------------//

    //--------------------------VARIABLES------------------------------------//
    static fs sc = new fs();
    static OutputStream outputStream = System.out;
    static Printer w = new Printer(outputStream);
    //-----------------------------------------------------------------------//

    //--------------------------ADMIN_MODE-----------------------------------//
    private static void ADMIN_MODE() throws IOException {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            w = new Printer(new FileOutputStream("output.txt"));
            sc = new fs(new FileInputStream("input.txt"));
        }
    }
    //-----------------------------------------------------------------------//

    //----------------------------START--------------------------------------//
    public static void main(String[] args)
            throws IOException {

        ADMIN_MODE();

        int t = sc.ni();while(t-->0)
            solve();


        w.close();
    }

    static int n;

    static void solve() throws IOException {
         n = sc.ni();
        List<pr> li = new ArrayList<>();
        HashMap<Integer, List<pr>> left = new HashMap<>();
        HashMap<Integer, List<pr>> right = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int l = sc.ni(), r = sc.ni();
            pr curr = new pr(l, r);
            li.add(curr);
            if(left.containsKey(l)) {
                left.get(l).add(curr);
            } else {
                List<pr> cl = new ArrayList<>();
                cl.add(curr);
                left.put(l, cl);
            }

            if(right.containsKey(r)) {
                right.get(r).add(curr);
            } else {
                List<pr> cl = new ArrayList<>();
                cl.add(curr);
                right.put(r, cl);
            }
        }
        uf<pr> uf = new uf<>(li);
        long ans = 0;

        for(int i: left.keySet()) {
            List<pr> cl = left.get(i);
            for(int j = 0; j < cl.size()-1; j++) {
                if(uf.connected(cl.get(j), cl.get(j+1))) continue;
                if(uf.componentSize(cl.get(j)) > 2) {
                    ans ++;
                }
                uf.unify(cl.get(j), cl.get(j+1));
            }
        }

        for(int i: right.keySet()) {
            List<pr> cl = right.get(i);
            for(int j = 0; j < cl.size()-1; j++) {
                if(uf.connected(cl.get(j), cl.get(j+1))) continue;
                if(uf.componentSize(cl.get(j)) >= 2) {
                    ans ++;
                }
                uf.unify(cl.get(j), cl.get(j+1));
            }
        }

        long num = (long) n *(n-1)*(n-2);
        num/=6;
        w.p(num-ans);
    }

    // region pow(a, b, mod) -> a^b
        static long fpow (long b, long x, int mod) {
            if (x == 0) return 1;
            if (x == 1) return b;
            if (x % 2 == 0) return fpow (b * b % mod, x / 2, mod) % mod;

            return b * fpow (b * b % mod, x / 2, mod) % mod;
        }
        // endregion

    static class pr implements Comparable<pr>{
        int a, b;

        public pr(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public int compareTo(pr p) {
            if(a==p.a && b==p.b) return 0;
            else return Integer.compare(a, p.a);
        }
    }

    /*find, connected, component size, size, components, unify*/

    static class uf<T extends Comparable<T>> {
        private int size;
        private int[] sz;
        private int[] id;
        private int numComponents;

        private Hashtable<T, Integer> ht;

        public uf(List<T> list) {
            ht = new Hashtable<>(list.size());

            for(int i = 0; i < list.size(); i++) ht.put(list.get(i), i);

            this.size = numComponents = list.size();
            sz = new int[list.size()];
            id = new int[list.size()];

            for(int i = 0; i < list.size(); i++) {
                id[i] = i;
                sz[i] = 1;
            }
        }

        public int find (T elem) { // with path compression

            int p = ht.get(elem);
            int root = p;
            while(id[root] != root) root = id[root];

            while(p != root) {
                int next = id[p];
                id[p] = root;
                p = next;
            }

            return root;
        }

        public boolean connected(T p, T q) { return find(p) == find(q); }

        public int componentSize(T p) { return sz[find(p)]; }

        public int size() { return size; }

        public int components() { return numComponents; }

        public void unify (T p, T q) {

            int root1 = find(p);
            int root2 = find(q);

            if(root1 == root2) return;

            if(sz[root1] < sz[root2]) {
                sz[root2] += sz[root1];
                id[root1] = root2;
            } else {
                sz[root1] += sz[root2];
                id[root2] = root1;
            }
            numComponents--;
        }
    }
    // endregion
}