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


public class Main {
	
	static class Scanner
	{
	    BufferedReader buf;
	    StringTokenizer tok;
	    Scanner()
	    {
	        buf = new BufferedReader(new InputStreamReader(System.in));
	    }
	    
	    boolean hasNext()
	    {
	        while(tok == null || !tok.hasMoreElements()) 
	        {
	            try
	            {
	                tok = new StringTokenizer(buf.readLine());
	            } 
	            catch(Exception e) 
	            {
	                return false;
	            }
	        }
	        return true;
	    }
	    
	    String next()
	    {
	        if(hasNext()) return tok.nextToken();
	        return null;
	    }
	    
	    int nextInt()
	    {
	        return Integer.parseInt(next());
	    }
	    
	    long nextLong()
	    {
	        return Long.parseLong(next());
	    }
	    
	    double nextDouble()
	    {
	        return Double.parseDouble(next());
	    }
	    
	}
	
	static class candy{
		int like;
		int num;
		candy(int l, int n) {
			like = l;
			num = n;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int q = sc.nextInt();
		while(q-- > 0) {
			int n = sc.nextInt();
			HashMap<Integer,Integer> map = new HashMap<>();
			List<candy> list = new ArrayList<>();
			int idx = 0;
			for(int i = 0; i < n; i++) {
				int num = sc.nextInt(), f = sc.nextInt();
				if(map.containsKey(num)) {
					candy c = list.get(map.get(num));
					c.num++;
					c.like += f;
				}
				else {
					map.put(num,idx++);
					list.add(new candy(f,1));
				}
			}
			Collections.sort(list,(a,b)->(a.num-b.num == 0 ? a.like-b.like : a.num-b.num));
			int max = list.get(list.size()-1).num,sum = 0, like = 0;
			for(int i = list.size()-1; i >= 0; i--) {
				max = Math.min(list.get(i).num, max);
				if(max == 0) break;
				sum += max;
				int cur = i, max_like = list.get(i).like, max_idx = cur;
				while(cur > 0) {
					if(list.get(cur-1).num < max) break;
					cur--;
					if(list.get(cur).like > max_like) {
						max_idx = cur;
						max_like = list.get(cur).like;
					}
				}
				like += Math.min(max,max_like);
				max--;
				if(max_idx != i) list.remove(max_idx); 
			}
			out.print(sum + " ");
			out.println(like);
		}
		out.close();
	}
	
	
    
   
}