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

public class Main {
    static int inf = (int) 1e9;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int t = nextInt();
        while (t-- > 0) {
            int n = nextInt();
            sweet a[] = new sweet[n];
            for (int i = 0; i < n; i++) a[i] = new sweet();
            for (int i = 0; i < n; i++) {
                int num = nextInt() - 1;
                int bad = nextInt();
                if (bad == 1) a[num].a++;
                else a[num].b++;
            }
            Arrays.sort(a, new sweet());
            ArrayList<Integer> id = new ArrayList<>();
            int ans1 = 0;
            for (int i = 0; i < n; i++) {
                if (a[i].a + a[i].b > id.size()) {
                    id.add(i);
                }
            }
            int cnt[] = new int[id.size()];
            int last = inf;
            for (int i = id.size() - 1; i >= 0; i--) {
                int k = a[id.get(i)].a + a[id.get(i)].b;
                cnt[i] = Math.min(k, last - 1);
                ans1 += cnt[i];
                last = cnt[i];
            }
            TreeMap<Integer, Integer> bad_cnt = new TreeMap<>();
            int ans2 = 0;
            int cnt_sz = id.size() - 1;
            for (int i = n - 1; i >= 0; i--) {
                if (i == 0) {
                    if (!bad_cnt.containsKey(a[i].a)) bad_cnt.put(a[i].a, 0);
                    bad_cnt.put(a[i].a, bad_cnt.get(a[i].a) + 1);
                }
                while (cnt_sz >= 0 && (cnt[cnt_sz] > a[i].a + a[i].b || i == 0)) {
                    ans2 += Math.min(bad_cnt.lastKey(), cnt[cnt_sz]);
                    bad_cnt.put(bad_cnt.lastKey(), bad_cnt.lastEntry().getValue() - 1);
                    if (bad_cnt.lastEntry().getValue() == 0) bad_cnt.pollLastEntry();
                    cnt_sz--;
                }
                if (!bad_cnt.containsKey(a[i].a)) bad_cnt.put(a[i].a, 0);
                bad_cnt.put(a[i].a, bad_cnt.get(a[i].a) + 1);
            }
            pw.println(ans1 + " " + ans2);
        }
        pw.close();
    }

    static BufferedReader br;
    static StringTokenizer st = new StringTokenizer("");

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public static String next() throws IOException {
        if (!st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }
}

class sweet implements Comparator<sweet> {
    int a, b;

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

    sweet() {
    }

    @Override
    public int compare(sweet o1, sweet o2) {
        return Integer.compare(o1.a + o1.b, o2.a + o2.b);
    }
}