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

 
public class TestClass {
    public static void main(String args[] ) throws Exception 
       {
           Scanner sc=new Scanner(System.in);
           int t=sc.nextInt();
           while(t--!=0)
           {
               int n=sc.nextInt();
               pair a[]=new pair[n];
               int i;
             int b[]=new int[n];
             for(i=0;i<n;i++)
             {
                 b[i]=sc.nextInt();
             }
             int c[]=new int[n];
             for(i=0;i<n;i++)
             {
                 c[b[i]-1]++;
             }
             for(i=0;i<n;i++)
             {
                 a[i]=new pair(b[i],c[b[i]-1]);
             }
               
                 Arrays.sort(a, new Comparator<pair>() { 
            @Override public int compare(pair p1, pair p2) 
            { 
                return p2.s - p1.s; 
            } 
        });
        LinkedHashMap<Integer,Integer> h=new LinkedHashMap<Integer,Integer>();
        
        for(i=0;i<n;i++)
        {
          h.put(a[i].f,a[i].s);
        }
        long sum=0;
        int max=Integer.MAX_VALUE;
        for(Integer key:h.keySet())
        {
            int v=h.get(key);
            if(max>v)
            {
                max=v;
                sum+=max;
                max=max-1;
            }
            else
            {
                if(max==0)
                break;
                sum+=max;
                max=max-1;
            }
        }
        System.out.println(sum);
           
}
}
}
class pair{
    int f,s;
    pair(int f,int s)
    {
        this.f=f;
        this.s=s;
    }
}