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.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution 
{
    public static class pair implements Comparable<pair>
    {
        int f0,f1;
        pair(int a0,int a1)
        {
            f0 = a0;
            f1 = a1;
        }
        public int compareTo(pair p1)
        {
            // if(this.f1+this.f0 == p1.f1+p1.f0)
            // {
            return(p1.f1-this.f1);
            // }
            // return(((p1.f1+p1.f0)-(this.f0+this.f1)));
        }
    }
    public static void main(String[] args) throws Exception 
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter w = new PrintWriter(System.out);
        int q = Integer.parseInt(in.readLine());
        for(int x=0;x<q;x++)
        {
            int n = Integer.parseInt(in.readLine());
            ArrayList<pair> pr = new ArrayList<pair>();
            int[] cns = new int[n+1];
            for(int i=0;i<=n;i++)
            {
                pr.add(new pair(0,0));
            }
            for(int i=0;i<n;i++)
            {
                String[] s1 = in.readLine().trim().split("\\s+");
                int type = Integer.parseInt(s1[0]);
                int f = Integer.parseInt(s1[1]);
                pair pq = pr.get(type);
                pq.f0 = pq.f0-(f-1);
                pq.f1 = pq.f1+f;
                pr.set(type,pq);
                cns[type]++;
            }
            Collections.sort(pr);
            Arrays.sort(cns);
            int prev = 10000000;
            int count = 0;
            int f1count = 0;
            ArrayList<Integer> take = new ArrayList<Integer>();
            for(int i=n;i>=0;i--)
            {
                int fr = cns[i];
                if(prev<=0)
                    break;
                count += (int)Math.min(prev-1,fr);
                take.add((int)Math.min(prev-1,fr));
                prev = (int)Math.min(prev-1,fr);
            }
            int ix = 0;
            for(int i=0;i<take.size();i++)
            {
                int total = take.get(i);
                int index = i;
                int maxf1s = Integer.MIN_VALUE;
                for(int j=0;j<pr.size();j++)
                { 
                    if(pr.get(j).f1+pr.get(j).f0>=total)
                    {
                        if(maxf1s<pr.get(j).f1)
                        {
                            maxf1s = pr.get(j).f1;
                            index = j;
                        }
                    }
                }
                f1count += (int)Math.min(maxf1s,total);
                pr.remove(index);
            }
            w.println(count+" "+f1count);
        }
        w.close();
    }
}