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

public class Main {
    void solve() throws FileNotFoundException, IOException {
        int q = ni();
        for (int i = 0; i < q; i++) {
            int n = ni();
            Type[] a = new Type[n];
            for (int j = 0; j < n; j++) {
                a[j] = new Type();
            }
            for (int j = 0; j < n; j++) {
                Type t = a[ni() - 1];
                t.c++;
                if (ni() == 1) {
                    t.f++;
                }
            }
            Arrays.sort(a, (Type o1, Type o2) -> {
                int r = Integer.compare(o1.c, o2.c);
                if (r == 0) {
                    return Integer.compare(o1.f, o2.f);
                } else {
                    return r;
                }
            });
            int last = a[n - 1].c + 1;
            int c = 0;
            int f = 0;
            PriorityQueue<Type> pq = new PriorityQueue<>();
            int nextToAdd = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                while ((nextToAdd >= 0) && (a[nextToAdd].c >= last - 1)) {
                    pq.add(a[nextToAdd]);
                    nextToAdd--;
                }
                if (pq.isEmpty()) {
                    last = a[j].c + 1;
                    while ((nextToAdd >= 0) && (a[nextToAdd].c >= last - 1)) {
                        pq.add(a[nextToAdd]);
                        nextToAdd--;
                    }
                }
                Type t = pq.poll();
                if (t.c >= last) {
                    last = last - 1;
                } else {
                    last = t.c;
                }
                if (last < 1) break;
                c += last;
                f += Math.min(t.f, last);
            }
            write(c + " " + f + "\n");
        }
    }

    class Type implements Comparable<Type> {
        public int c, f;

        @Override
        public int compareTo(Type type) {
            return -Integer.compare(this.f, type.f);
        }
    }

    public static void main(String[] args) throws FileNotFoundException, IOException {
        Main m = new Main();
        m.solve();
        try {
            m.out.close();
        } catch (IOException e) {}
    }

    BufferedReader in;
    BufferedWriter out;
    StringTokenizer tokenizer;
    public Main() {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String n() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(in.readLine());
            } catch (IOException e) {}
        }
        return tokenizer.nextToken();
    }
    public int ni() {
        return Integer.parseInt(n());
    }
    public long nl() {
        return Long.parseLong(n());
    }
    public void write(String s) {
        try {
            out.write(s);
        } catch (IOException e) {}
    }
}