Problem: This problem is actually a subproblem of problem G from the same contest.

There are n candies in a candy box. The type of the i-th candy is a_i (1 ≤ a_i ≤ n).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type 1 and two candies of type 2 is bad). 

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

Your task is to find out the maximum possible size of the single gift you can prepare using the candies you have.

You have to answer q independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries. Each query is represented by two lines.

The first line of each query contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of candies.

The second line of each query contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n), where a_i is the type of the i-th candy in the box.

It is guaranteed that the sum of n over all queries does not exceed 2 ⋅ 10^5.

Output

For each query print one integer — the maximum possible size of the single gift you can compose using candies you got in this query with the restriction described in the problem statement.

Example

Input


3
8
1 4 8 4 5 6 3 8
16
2 1 3 3 4 3 4 4 1 3 2 2 2 4 1 1
9
2 2 4 4 4 7 7 7 7


Output


3
10
9

Note

In the first query, you can prepare a gift with two candies of type 8 and one candy of type 5, totalling to 3 candies.

Note that this is not the only possible solution — taking two candies of type 4 and one candy of type 6 is also valid.

Solution (in JAVA):

Solution:

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



public class Main {

    public static void main(String[] args) throws Exception {
        IO io ;
        try {
            io = new IO("in.in", null);
        } catch (IOException e) {
            io = new IO(null, null);
        }
        int T = io.getNextInt();
        ArrayList<item> A = new ArrayList<>();
        HashMap<Integer,int[]> HM = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int t = 0;t < T;t++) {
            int n = io.getNextInt();
            A.clear();
            HM.clear();
            pq.clear();
            for (int i = 0;i < n;i++) {
                int w = io.getNextInt();
                int f = io.getNextInt();
                if (!HM.containsKey(w)) HM.put(w,new int[2]);
                HM.get(w)[f]++;
            }
            for (int w : HM.keySet()) {
                int [] C = HM.get(w);
                A.add(new item(C[0] + C[1],C[1]));
            }
            Collections.sort(A);
            Collections.reverse(A);
            int i = 0;
            int upper = n;
            int w = 0,f = 0;

            while ((!pq.isEmpty() || i < A.size()) && upper > 0) {
                while (i < A.size() && A.get(i).n >= upper) {
                    pq.add(-A.get(i).f);
                    i++;
                }
                if (pq.isEmpty()) {
                    int c = A.get(i).n;
                    upper = Math.min(upper,c);
                }
                else {
                    w += upper;
                    int ef = -pq.poll();
                    ef = Math.min(ef,upper);
                    f += ef;
                    upper--;
                }
            }
            io.println(w + " " + f);
        }
        io.close();
    }
    private static final int onebillion7 = 1000000007;
}

class item implements Comparable<item>{
    int n,f;
    public item(int a,int b) {
        n = a;
        f = b;
    }
    @Override
    public int compareTo(item o) {
        if (n == o.n) return f - o.f;
        return n - o.n;
    }
}


class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}