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 implements Runnable {
	public static void main (String[] args) {new Thread(null, new Main(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		int q = fs.nextInt();
		while(q-->0) {
			int n = fs.nextInt();
			int[] a = new int[n];
			int[][] data = new int[n][2];
			for(int i = 0; i < n; i++) {
				a[i] = fs.nextInt();
				data[i][0] = a[i];
				data[i][1] = fs.nextInt();
			}
			sort(a);
			long res = 0;
			ArrayList<Integer> list = new ArrayList<>();
			for(int i = 0; i < n; i++) {
				int j = i;
				while(j < n && a[i] == a[j]) j++;
				int len = j-i;
				list.add(len);
				i = --j;
			}
			Collections.sort(list, Collections.reverseOrder());
			int lim = Integer.MAX_VALUE;
			ArrayList<Integer> sizes = new ArrayList<>();
			for(int i : list) {
				if(lim <= 0) break;
				if(i < lim) {
					sizes.add(i);
					res += i;
					lim = i-1;
				}
				else {
					res += lim;
					sizes.add(lim);
					lim--;
				}
			}
			HashMap<Integer, Integer> map = new HashMap<>();
			ArrayList<Group> list2 = new ArrayList<>();
			for(int i = 0; i < data.length; i++) {
				int v = data[i][0];
				if(!map.containsKey(v)) {
					map.put(v, list2.size());
					list2.add(new Group(v));
				}
				int loc = map.get(v);
				list2.get(loc).freq++;
				if(data[i][1] == 1)
					list2.get(loc).count1++;
			}
			Collections.sort(list2);
			int[] cnt = new int[list2.size()];
			for(int i = 0; i < list2.size(); i++ ) {
				cnt[i] = list2.get(i).count1;
			}
			ST st = new ST(cnt.length, cnt.clone());
			long max = 0;
			int ptr = list2.size()-1;
			for(int i : sizes) {
				while(ptr >= 0 && list2.get(ptr).freq >= i) ptr--;
				ptr++;
				int idx = st.query(1, ptr, cnt.length-1);
				max += Math.min(cnt[idx], i);
				cnt[idx] = -1;
				st.kill(1, idx);
			}
			out.println(res + " " + max);
		}
		
		out.close();
	}
	
	class Group implements Comparable<Group> {
		int type, freq, count1;
		Group(int t) {
			type = t;
		}
		public int compareTo(Group g) {
			return Integer.compare(freq, g.freq);
		}
	}
	
	class ST {
		int n;
		int[] lo, hi;
		int[] maxIdx, vals;
		ST(int a, int[] v) {
			n = 4*a+100;
			lo = new int[n]; hi = new int[n];
			maxIdx = new int[n]; vals = v;
			init(1, 0, a-1);
		}
		void init(int p, int l, int r) {
			lo[p] = l; hi[p] = r;
			if(l == r) {
				maxIdx[p] = l;
				return;
			}
			int mid = (l+r)/2;
			int lf = 2*p, rg = 1+lf;
			init(lf, l, mid);
			init(rg, mid+1, r);
			if(vals[maxIdx[lf]] > vals[maxIdx[rg]]) maxIdx[p] = maxIdx[lf];
			else maxIdx[p] = maxIdx[rg];
		}
		int query(int p, int L, int R) {
			if(hi[p] < L || R < lo[p]) return -1;
			if(L <= lo[p] && hi[p] <= R) {
				return maxIdx[p];
			}
			int lf = 2*p, rg = 1+lf;
			int k1 = query(lf, L, R);
			int k2 = query(rg, L, R);
			if(k1 == -1) return k2;
			if(k2 == -1) return k1;
			if(vals[k1] > vals[k2]) return k1;
			return k2;
		}
		void kill(int p, int idx) {
			if(lo[p] == hi[p]) {
				vals[idx] = -1;
				return;
			}
			int lf = 2*p, rg = 1+lf;
			if(lo[lf] <= idx && idx <= hi[lf]) kill(lf, idx);
			else kill(rg, idx);
			if(maxIdx[lf] == -1) maxIdx[p] = maxIdx[rg];
			else if(maxIdx[rg] == -1) maxIdx[p] = maxIdx[lf];
			else {
				if(vals[maxIdx[lf]] > vals[maxIdx[rg]]) maxIdx[p] = maxIdx[lf];
				else maxIdx[p] = maxIdx[rg];
			}
			
		}
	}
	
	void sort(int[] a) {
		Random rand = new Random();
		int n = a.length;
		for(int i = 0; i < n; i++) {
			int x = rand.nextInt(n);
			int y = rand.nextInt(n);
			int t = a[x]; a[x] = a[y]; a[y] = t;
		}
		Arrays.sort(a);
	}
	
	int sum(int a) {
		int sum = 0;
		while(a > 0) {
			sum += a % 10;
			a /= 10;
		}
		return sum % 4;
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}