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:
/*
* @Author: patan
* @Date:   2019-06-27 15:59:14
* @Last Modified by:   patan
* @Last Modified time: 2019-06-27 16:01:23
*/
import java.io.*;
import java.util.*;
 
public class temp {

	public static void main(String[] args)throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
		int t = in.nextInt();
		int n; int arr[]; int val; int ans,ans2; int typecount[]; int countkitypes[];
		int typefzero[];
		int type;
		int fval;
		LinkedList<Integer>indices = new LinkedList<Integer>();
		for(int i=0;i<t;i++)
		{
			n=in.nextInt();
			// arr = new int[n];
			typecount = new int[n+1];
			typefzero = new int[n+1];
			Arrays.fill(typefzero,0);
			Arrays.fill(typecount,0);
			countkitypes = new int[n+1];
			Arrays.fill(countkitypes,-1);
			for(int j=0;j<n;j++){
				type = in.nextInt();
				typecount[type]++;
				if(in.nextInt()==0)
					typefzero[type]++;
			}
			for(int j=1;j<n+1;j++)
			{
				if(typecount[j]!=0)
					indices.add(j);
			}
			// out.println(indices);
			int j;
			while(indices.size()>0)
			{
				j=indices.remove();
				val = typecount[j];
				fval = typefzero[j];
				// out.println("j= "+j+";val="+val+";fval="+fval);
				// out.println(j);
				while(val>0)
				{
					if(countkitypes[val]==-1){
						countkitypes[val]=j;
						break;
					}
					else if(fval<typefzero[countkitypes[val]])
					{
						// out.println("adding "+countkitypes[val]);
						indices.add(countkitypes[val]);
						countkitypes[val]=j;
						break;
					}
					val-=1;
					if(fval>0)
						fval-=1;
				}
				// out.println("j= "+j+";val="+val+";fval="+fval);
				typecount[j] = val;
				typefzero[j] = fval;
			}
			ans=0; ans2=0;
			for(j=1;j<n+1;j++)
			{
				if(countkitypes[j]!=-1){
					ans+=j;
					ans2+=typefzero[countkitypes[j]];
				}
			}
			out.println(ans+" "+(ans-ans2));
		}

        out.close();
	}
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

    }

}