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 [] arr1 = new int[n + 1];
            int [][] arr2 = new int[n + 1][2];
            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);
            int sz2 = 0;
            int sz1 = 0;
            int [] f = new int[n + 1];

            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;
                f[last]++;
            }

            // f -> unwanted count
            Map<Integer, List<Integer>> fmap = new HashMap<>();
            for (int i = 1; i <= n; ++i) {
                if (arr2[i][0] == 0) continue;
                List<Integer> list = fmap.computeIfAbsent(arr2[i][0], ArrayList::new);
                list.add(arr2[i][1]);
            }
            PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
            for (int i = n; i > 0; --i) {
                // try to pick i candies
                if (fmap.containsKey(i)) q.addAll(fmap.get(i));
                if (f[i] != 0) {
                    sz2 += Math.min(q.peek(), i);
                    q.poll();
                }

            }
            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();
    }
    
}