This problem is a version of problem D from the same contest with some additional constraints and tasks.

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.

You really like some of the candies and don't want to include them into the gift, but you want to eat them yourself instead. For each candy, a number f_i is given, which is equal to 0 if you really want to keep i-th candy for yourself, or 1 if you don't mind including it into your gift. It is possible that two candies of the same type have different values of f_i.

You want your gift to be as large as possible, but you don't want to include too many of the candies you want to eat into the gift. So, you want to calculate the maximum possible number of candies that can be included into a gift, and among all ways to choose maximum number of candies, you want to maximize the number of candies having f_i = 1 in your gift.

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.

The first line of each query contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of candies.

Then n lines follow, each containing two integers a_i and f_i (1 ≤ a_i ≤ n, 0 ≤ f_i ≤ 1), where a_i is the type of the i-th candy, and f_i denotes whether you want to keep the i-th candy for yourself (0 if you want to keep it, 1 if you don't mind giving it away).

It is guaranteed that the sum of n over all queries does not exceed 2 ⋅ 10^5.

Output

For each query print two integers:

  * the maximum number of candies in a gift you can compose, according to the constraints in the statement; 
  * the maximum number of candies having f_i = 1 in a gift you can compose that contains the maximum possible number of candies. 

Example

Input


3
8
1 0
4 1
2 0
4 1
5 1
6 1
3 0
2 0
4
1 1
1 1
2 1
2 1
9
2 0
2 0
4 1
4 1
4 1
7 0
7 1
7 0
7 1


Output


3 3
3 3
9 5

Note

In the first query, you can include two candies of type 4 and one candy of type 5. All of them have f_i = 1 and you don't mind giving them away as part of the gift.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Random;
import java.io.PrintWriter;
/*
    Solution Created: 19:16:39 26/06/2019
    Custom Competitive programming helper.
*/
public class Main {
	public static void main(String[] args) {
		Reader in = new Reader();
		Writer out = new Writer();
		Solution.solve(in, out);
		out.exit();
	}

static class Graph {
	private ArrayList<Integer> con[];
	private boolean[] visited;

	public Graph(int n) {
		con = new ArrayList[n];
		for (int i = 0; i < n; ++i)
			con[i] = new ArrayList();
		visited = new boolean[n];
	}

	public void reset() {
		Arrays.fill(visited, false);
	}

	public void addEdge(int v, int w) {
		con[v].add(w);
	}

	public void dfs(int cur) {
		visited[cur] = true;
		for (Integer v : con[cur]) {
			if (!visited[v]) {
				dfs(v);
			}
		}
	}

	public void bfs(int cur) {
		Queue<Integer> q = new LinkedList<>();
		q.add(cur);
		visited[cur] = true;
		while (!q.isEmpty()) {
			cur = q.poll();
			for (Integer v : con[cur]) {
				if (!visited[v]) {
					visited[v] = true;
					q.add(v);
				}
			}
		}
	}
}

static class Reader {
	static BufferedReader br;
	static StringTokenizer st;
	private int charIdx = 0;
	private String s;

	public Reader() {
		this.br = new BufferedReader(new InputStreamReader(System.in));
	}

	public int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public double[] nd(int n) {
		double[] a = new double[n];
		for (int i = 0; i < n; i++)
			a[i] = nextDouble();
		return a;
	}

	public char nextChar() {
		if (s == null || charIdx >= s.length()) {
			if (st == null || !st.hasMoreTokens())
				try {
					readLine();
				} catch (Exception e) {
				}
			s = st.nextToken();
			charIdx = 0;
		}
		return s.charAt(charIdx++);
	}

	public long[] nl(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}

	public char[] nca() {
		return next().toCharArray();
	}

	public String[] nS(int n) {
		String[] a = new String[n];
		for (int i = 0; i < n; i++)
			a[i] = next();
		return a;
	}

	public int nextInt() {
		if (st == null || !st.hasMoreTokens())
			try {
				readLine();
			} catch (Exception e) {
			}
		return Integer.parseInt(st.nextToken());
	}

	public double nextDouble() {
		if (st == null || !st.hasMoreTokens())
			try {
				readLine();
			} catch (Exception e) {
			}
		return Double.parseDouble(st.nextToken());
	}

	public Long nextLong() {
		if (st == null || !st.hasMoreTokens())
			try {
				readLine();
			} catch (Exception e) {
			}
		return Long.parseLong(st.nextToken());
	}

	public String next() {
		if (st == null || !st.hasMoreTokens())
			try {
				readLine();
			} catch (Exception e) {
			}
		return st.nextToken();
	}

	public static void readLine() {
		try {
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
		}
	}
}

static class Solution {
	public static void solve(Reader in, Writer out) {
		int q = in.nextInt();
		while(q-->0) {
			int n = in.nextInt();
			int[] f = new int[n+2];
			int[] WE = new int[n+2];
			for(int i = 0; i<n; i++) {
				int a = in.nextInt();
				int b = in.nextInt()==1?0:1;
				f[a]++;
				WE[a]+=b;
			}
			PriorityQueue<Pair> cont = new PriorityQueue<>(Collections.reverseOrder());
			for(int i = 0; i<n+1; i++) {
				if(f[i]>0) {
					cont.add(new Pair(i, f[i], WE[i]));
				}
			}
			int ans1 = 0;
			int ans2 = 0;
			while(!cont.isEmpty()) {
				Pair p = cont.poll();
				//System.out.println(p.id+" "+p.val+" "+p.wannaEeat);
				ans1+=p.val;
				ans2+=p.val-p.wannaEeat;
				if(p.val<=1) break;
				while((!cont.isEmpty())&&cont.peek().val==p.val) {
					Pair pop = cont.poll();
					cont.add(new Pair(pop.id, pop.val-1, Math.max(0, pop.wannaEeat-1)));
				}
			}
			System.out.println(ans1+" "+ans2);
		}
	}
	static class Pair implements Comparable<Pair>{
		int id;
		int val;
		int wannaEeat;
		public Pair(int id, int val, int wannaEat) {
			this.id = id;
			this.val = val;
			this.wannaEeat = wannaEat;
		}
		@Override
		public int compareTo(Pair o) {
			if(this.val == o.val) {
				return o.wannaEeat - this.wannaEeat;
			}
			return this.val - o.val;
		}
	}
}

static class Sort {
	private static Random random = new Random();
	public static void sortArray(int[] s) {
        shuffle(s);
        Arrays.sort(s);
    }
	public static void sortArray(long[] s) {
        shuffle(s);
        Arrays.sort(s);
    }
	public static void sortArray(String[] s) {
        shuffle(s);
        Arrays.sort(s);
    }
	public static void sortArray(char[] s) {
        shuffle(s);
        Arrays.sort(s);
    }
    private static void shuffle(int[] s) {
        for (int i = 0; i < s.length; ++i) {
            int j = random.nextInt(i + 1);
            int t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
    private static void shuffle(long[] s) {
        for (int i = 0; i < s.length; ++i) {
            int j = random.nextInt(i + 1);
            long t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
    private static void shuffle(String[] s) {
        for (int i = 0; i < s.length; ++i) {
            int j = random.nextInt(i + 1);
            String t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
    private static void shuffle(char[] s) {
        for (int i = 0; i < s.length; ++i) {
            int j = random.nextInt(i + 1);
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
}

static class Util{
	    static boolean isPrime(int n) { 
	        if (n <= 1) return false; 
	        if (n <= 3) return true; 
	        if (n % 2 == 0 || n % 3 == 0) return false; 
	        for (int i = 5; i * i <= n; i = i + 6) 
	            if (n % i == 0 || n % (i + 2) == 0) 
	            return false; 
	        return true; 
	    }
		public static int upperBound(long[] a, long v) {
			if(a[0]>v) return -1;
			int l=0,h=a.length-1;
			while(l<h) {
				int mid = (l+h)/2;
				if(v>=a[mid]) l = mid+1;
				else h = mid-1;
			}
			if(v<a[l]) return l-1;
			return l;
		}
		public static int lowerBound(long[] a, int v) {
			if(a[a.length-1]<v) return -1;
			int l=0,h=a.length-1;
			while(l<h) {
				int mid = (l+h)/2;
				if(v<=a[mid]) h = mid-1;
				else l = mid+1;
			}
			if(v>a[l]) return l+1;
			return l;
		}
	    public static boolean[] getSieve(int n) {
	        boolean[] isPrime = new boolean[n+1];
	        for (int i = 2; i <= n; i++) isPrime[i] = true;
	        for (int i = 2; i*i <= n; i++) if (isPrime[i]) 
	                for (int j = i; i*j <= n; j++) isPrime[i*j] = false;
	        return isPrime;
	    }
	    public static int gcd(int a, int b) { 
	        if (a == 0) 
	            return b; 
	        return gcd(b%a, a); 
	    }
		public static long modAdd(long a, long b, long mod) {
			return (a%mod+b%mod)%mod;
		}
		public static long modMul(long a, long b, long mod) {
			return ((a%mod)*(b%mod))%mod;
		}
		public static void dbg(Object... o) { 
			System.out.println(Arrays.deepToString(o)); 
		}
	}

static class Writer {
	private PrintWriter pw;
	public Writer(){
		pw = new PrintWriter(System.out);
	}
	
	public void printArray(int[] a) {
		for(int i = 0; i<a.length; i++) print(a[i]+" ");
	}
	public void printlnArray(int[] a) {
		for(int i = 0; i<a.length; i++) print(a[i]+" ");
		pw.println();
	}
	public void printArray(long[] a) {
		for(int i = 0; i<a.length; i++) print(a[i]+" ");
	}
	public void printlnArray(long[] a) {
		for(int i = 0; i<a.length; i++) print(a[i]+" ");
		pw.println();
	}
	public void print(Object o) {
		pw.print(o.toString());
	}
	public void println(Object o) {
		pw.println(o.toString());
	}
	public void flush() {
		pw.flush();
	}
	public void exit() {
		pw.close();
	}
}
}
