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.*;

/**
 * @author kenpen
 */
public class CandyBoxHard
{
    public static void main(String...args)
    {
        int t = getInt();
        while (t-- > 0) {
            int n = getInt();
//            int [][] arr = new int[n][2];
            int [] arr1 = new int[n + 1];
            int [][] arr2 = new int[n + 1][2];
            PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>()
            {
                @Override
                public int compare(int[] o1, int[] o2)
                {
                    if (o1[0] == o2[0]) return o2[1] - o1[1];
                    return o2[0] - o1[0];
                }
            });
            for (int i = 0 ; i < n ; ++i) {
                int cn = getInt();
                int fi = getInt();
                arr1[cn]++;
                arr2[cn][0]++;
                arr2[cn][1] += fi; // increase number of unwanted candies.
            }
            Arrays.sort(arr1);
            for (int i = 0 ; i <= n ; ++i) {
                if (arr2[i][0] != 0) q.add(arr2[i]);
            }
            int sz2 = 0;
//            List<int[]> sol2 = new ArrayList<>();
            List<int[]> temp = new ArrayList<>();
            while (!q.isEmpty() && q.peek()[0] > 0) {
//                int ele = q.peek()[0];
                temp.clear();
                int[] ele = q.poll();
//                int max = q.peek()[1];
//                int maxi = 0;
                while (!q.isEmpty() && q.peek()[0] == ele[0]) {
//                    int[] mist = q.poll();
                    temp.add(q.poll());
//                    if (mist[1] > max) {
//                        maxi = temp.size() - 1;
//                        max = mist[1];
//                    }
                }
                // pick maxi;
//                sol2.add(temp.get(maxi));
//                sz2 += temp.get(maxi)[1];
                sz2 += ele[1];
                for (int[] mist : temp) {
                    if (mist[0] == mist[1])
                        mist[1]--;
                    mist[0]--;
                    q.add(mist);
                }
            }

            int last = Integer.MAX_VALUE;
            int sz = 0;

            for (int i = n; i >= 0; --i) {
                if (arr1[i] == 0 || last <= 0) break;
                if (arr1[i] >= last) {
                    last--;
                }
                else {
                    last = arr1[i];
                }
                sz += last;
            }
//            print(arrayToString(arr));
            print(sz + " " + sz2, true);
        }
        flush();
    }

    // ===== Printing code =====
    static StringBuilder buf = new StringBuilder();
    static int bufSize = 5000;
    static void print(String s) {print(s, false);}

    static void print(String s, boolean newLine) {
        buf.append(s);
        if (newLine) buf.append("\n");
        if (buf.length() >= bufSize) {
            System.out.print(buf);
            buf.delete(0, buf.length());
        }
    }

    static void flush() {
        System.out.print(buf);
        buf.delete(0, buf.length());
    }

    static String arrayToString(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int a : arr) sb.append(a).append(" ");
        if (arr.length > 0) sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    // ===== INPUT TAKING CODE ====
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static void checkSt() {
        if (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                System.out.println("Error parsing input");
            }
        }
    }
    static int getInt() {
        checkSt();
        return Integer.valueOf(st.nextToken());
    }

    static long getLong() {
        checkSt();
        return Long.valueOf(st.nextToken());
    }

    static long getNewLineLong() {
        try {
            return Long.valueOf(br.readLine());
        } catch (IOException e) {
            System.out.println("Error parsing input");
            return 0;
        }
    }

    static int getNewLineInt() {
        try {
            return Integer.valueOf(br.readLine());
        } catch (IOException e) {
            System.out.println("Error parsing input");
            return 0;
        }
    }

    static char getChar() {
        checkSt();
        return st.nextToken().charAt(0);
    }

    static String getStr() {
        checkSt();
        return st.nextToken();
    }

}