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.*;
import java.lang.*;
import java.math.*;
public class Main extends Thread  {
    boolean[] prime;
    FastScanner sc;
    PrintWriter pw;
    MathF mf;
    final class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

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

        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }

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

        public String nli() {
            String line = "";
            if (st.hasMoreTokens()) line = st.nextToken();
            else try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            while (st.hasMoreTokens()) line += " " + st.nextToken();
            return line;
        }

        public double nd() {
            return Double.parseDouble(next());
        }
    }
    final class MathF {
        long grtdiv(long x)
        {
            if(isPrime(x))
                return 1;
            else
            {
                long ans=0;
                long y=(long)Math.sqrt(x)+1;
                for(;y>=2;y--)
                {
                    if(x%y==0)
                        ans=Math.max(ans,Math.max(y,x/y));
                }
                return ans;
            }
        }
        boolean isPrime(long x)
        {
            for(int i=2;i*i<=x;i++)
            {
                if(x%i==0)
                {
                    return false;
                }
            }
            return true;
        }
        long[][] mul(long[][] arr,long[][] brr,int a,int b,int c,int d)
        {
            long[][] crr=new long[a][d];
            for(int i=0;i<a;i++)
            {
                for(int j=0;j<d;j++)
                {
                    for(int k=0;k<b;k++)
                    {
                        crr[i][j]+=(((arr[i][k]%1000000007)*(brr[k][j]%1000000007))%1000000007);
                    }
                }
            }
            return crr;
        }
        int sod(long a)
        {
            int ans=0;
            while(a!=0)
            {
                ans+=(a%10);
                a=a/10;
            }
            return ans;
        }
        long pow(long a,long b)
        {
            if(b==0)
                return 1;
            else
            {
                long x=pow(a,b/2);
                if(b%2==1)
                    return (x*x*a);
                else
                    return (x*x);
            }
        }
        public  long gcd(long a, long b) {
            return (b == 0 ? a : gcd(b, a % b));
        }
        public long exponent(long a,long b)
        {
            if(b==0)
                return 1;
            else
            {
                long x=exponent(a,b/2);
                x*=x;
                if(b%2==1)
                    x*=a;
                return x;
            }
        }
        public  int nod(long x) {
            int i = 0;
            while (x != 0) {
                i++;
                x = x / 10;
            }
            return i;
        }

        public  int nob(long x) {
            if(x==0)
                return 1;
            return (int) Math.floor(Math.log(x) / Math.log(2)) + 1;
        }

        public int[] FastradixSort(int[] f) {
            int[] to = new int[f.length];
            {
                int[] b = new int[65537];
                for (int i = 0; i < f.length; i++) b[1 + (f[i] & 0xffff)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < f.length; i++) to[b[f[i] & 0xffff]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            {
                int[] b = new int[65537];
                for (int i = 0; i < f.length; i++) b[1 + (f[i] >>> 16)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < f.length; i++) to[b[f[i] >>> 16]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            return f;
        }

        public  void Primesieve(int n) {
            prime=new boolean[n];
            for (int i = 0; i < n; i++)
                prime[i] = true;
            for (int p = 2; p * p < n; p++) {
                if (prime[p] == true) {
                    for (int i = p * p; i < n; i += p)
                        prime[i] = false;
                }
            }
        }
    }
    public Main(ThreadGroup t,Runnable r,String s,long d )
    {
        super(t,r,s,d);
    }
    public void run()
    {
        sc=new FastScanner();
        pw=new PrintWriter(System.out);
        mf=new MathF();
        solve();
        pw.flush();
        pw.close();
    }
    public static void main(String[] args)
    {
        new Main(null,null,"",1<<10).start();
    }

    /////////////------------------------------------/////////////
    /////////////------------------------------------/////////////
    ////////////------------------MAIN-LOGIC---------/////////////
    ////////////-------------------------------------/////////////
    ///////////--------------------------------------/////////////


    public void solve(){
        int t=sc.ni();
        while(t-->0) {
            int n = sc.ni();
            int[] frr=new int[n];
            int[] orr=new int[n];
            Arrays.fill(frr,0);
            Arrays.fill(orr,0);
            PriorityQueue<Integer> pq=new PriorityQueue();
            ArrayList<Integer>[] list=new ArrayList[n+1];
            for(int i=0;i<n;i++)
            {
                int x=sc.ni();
                x--;
                int y=sc.ni();
                frr[x]++;
                if(y==1)
                    orr[x]++;
                list[i]=new ArrayList<Integer>();
            }
            list[n]=new ArrayList<Integer>();
            for(int i=0;i<n;i++)
            {
                list[frr[i]].add(orr[i]);
            }
            long sum=0;
            long sum1=0;
            for(int c=n;c>=1;c--)
            {
                for(int x:list[c])
                {
                    pq.add(-x);
                }
                if(!pq.isEmpty())
                {
                    int z=-pq.poll();
                    sum+=c;
                    sum1+=(Math.min(z,c));
                }
            }
            pw.println(sum+" "+sum1);
        }
    }
}