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

import javax.lang.model.util.ElementScanner6;
import javax.swing.tree.TreeNode;

import java.io.*;

public class Main{

    public static void main(String[] args) {

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(inp, out);
        out.close();
        
        }



    static class Solver {


        class Node implements Comparable<Node>{
            int i;
            long c;
        
            Node(int i,long c)
            {
                this.i=i;
                this.c=c;


            }

        public int compareTo(Node n)
            {
                if(this.c==n.c)
                {
                    return Integer.compare(this.i, n.i);
                }
                return Long.compare(this.c, n.c);
            }
        }

        public boolean done(int[] sp,int[] par)
        {
            int root;

            root=findSet(sp[0],par);
            
        for(int i=1;i<sp.length;i++)
        {
                if(root!=findSet(sp[i], par))
                    return false;
        }
        return true;
        }
    public int findSet(int i,int[] par)
    {
        int x =i;
            boolean flag =false;
            while(par[i]>=0)
            {
                flag = true;
                i=par[i];
            }
            if(flag)
                par[x]=i;
            return i;
    }

    public void unionSet(int i,int j,int[] par)
    {
            int x = findSet(i, par);
            int y = findSet(j, par);
            if(x<y)
            {
                par[y]=x;
            }
            else
            {
                par[x]=y;
            }
    }

    public  long pow(long a, long b, long MOD) {
            if (b == 0) {
                return 1;
            }
            if (b == 1) {
                return a;
            }
            long val = pow(a, b / 2, MOD);
            if (b % 2 == 0) {
                return val * val % MOD;
            } else {
                return val * (val * a % MOD) % MOD;

            }
        
        }


        public void minPrimeFactor(int n,int[] s)
        {
            boolean prime[] = new boolean[n+1];
            Arrays.fill(prime, true);
            s[1]=1;
            s[2]=2;
            for(int i=4;i<=n;i+=2)
            {
                prime[i]=false;
                s[i]=2;
            }

            for(int i=3;i<=n;i+=2)
            {
                if(prime[i])
                {
                    s[i]=i;
                    for(int j=2*i;j<=n;j+=i)
                    {
                        prime[j]=false;
                        s[j]=i;
                    }
                }
            }
            
        }

        
        // public void findAllPrime(int n,ArrayList<Node> al,int s[])
        // {
        //     int curr = s[n];
        //     int cnt = 1;
        //     while(n>1)
        //     {
        //         n/=s[n];
        //         if(curr==s[n])
        //         {
        //             cnt++;
        //             continue;

        //         }
        //         Node n1 = new Node(curr,cnt);
        //         al.add(n1);

        //         curr=s[n];
        //         cnt=1;
        //     }
        // }

        

        public int binarySearch(int n,int k)
        {
            int left=1;
            int right=100000000+5;
            int ans=0;
            while(left<=right)
            {
                int mid = (left+right)/2;
                if(n/mid>=k)
                {
                    left = mid+1;
                    ans=mid;
                }
                else
                {
                    right=mid-1;
                }
            }

            return ans;
        }
        public boolean checkPallindrom(String s)
        {
            char ch[] = s.toCharArray();

            for(int i=0;i<s.length()/2;i++)
            {
                if(ch[i]!=ch[s.length()-1-i])
                    return false;
            }
            return true;
        }


        public void dfs_util(ArrayList<Integer>[] al,boolean vis[],int x,int lvl[],ArrayList<Integer>[] a)
        {
                
            vis[x] = true;
            
            // System.out.println("x "+x);
                for(int i=0;i<al[x].size();i++)
                {
                    
                    if(!vis[al[x].get(i)])
                    {
                        // System.out.println("s.size "+s.size());
                        lvl[al[x].get(i)]=1^lvl[x];
                        a[lvl[al[x].get(i)]].add(al[x].get(i));
                        dfs_util(al, vis, al[x].get(i),lvl,a);   
                        
                    }    
                    
                }

            
            
            
            
            return ;
        }

        public void dfs(ArrayList<Integer>[] al, int lvl[],ArrayList<Integer>[] a)
        {
            
            boolean vis[] = new boolean[al.length];
        
            int g =0;
            
            for(int i=0;i<al.length;i++)
            { 
            
            
                    if(!vis[i])
                    {
                        lvl[i]=0;
                        a[lvl[i]].add(i);
                        dfs_util(al,vis,i,lvl,a);
                        
                    }
                
            }

        


        }

        public void remove(ArrayList<Integer>[] al,int x)
        {
            for(int i=0;i<al.length;i++)
            {
                for(int j=0;j<al[i].size();j++)
                {

                    if(al[i].get(j)==x)
                        al[i].remove(j);

                }
            }
        }

        public long gcd(long a, long b) 
        { 
            if (a == 0) 
                return b; 
            return gcd(b % a, a); 
        }

      public  static String findSum(String str1, String str2)  
{  
   
    // Before proceeding further, make sure length  
    // of str2 is larger.  
    
    if (str1.length() > str2.length()){ 
        String t = str1; 
        str1 = str2; 
        str2 = t; 
    } 
  
    char ch1[] = new char[str1.length()];
    char ch2[]=  new char[str2.length()];
     ch1 = str1.toCharArray();
     ch2 =str2.toCharArray();
    // Take an empty String for storing result  
    String str = "";  
  
    // Calculate length of both String  
    int n1 = ch1.length, n2 = ch2.length;  
    int diff = n2 - n1;  
  
    // Initially take carry zero  
    int carry = 0;  
  
    // Traverse from end of both Strings  
    for (int i = n1 - 1; i>=0; i--)  
    {  
        // Do school mathematics, compute sum of  
        // current digits and carry  
        int sum = ((int)(ch1[i]-'0') +  (int)(ch2[i+diff]-'0') + carry);  
        str += (char)(sum % 10 + '0');  
        carry = sum / 10;  
    }  
  
    // Add remaining digits of str2[]  
    for (int i = n2 - n1 - 1; i >= 0; i--)  
    {  
        int sum = ((int)(ch2[i] - '0') + carry);  
        str += (char)(sum % 10 + '0');  
        carry = sum / 10;  
    }  
  
    // Add remaining carry  
    if (carry > 0)  
        str += (char)(carry + '0');  
  
    // reverse resultant String 
    return new StringBuilder(str).reverse().toString();   
}  

        public void printDivisors(long n,ArrayList<Long> al) 
        { 
            // Note that this loop runs till square root 
            for (long i=2; i<=Math.sqrt(n); i++) 
            { 
                if (n%i==0) 
                { 
                    // If divisors are equal, print only one 
                    if (n/i == i) 
                    {
                        
                            al.add(i);
                    }
                    
        
                    else // Otherwise print both 
                    {   
                            al.add(i); 
                            al.add(n/i);
                    }
                        
                } 
            } 
        } 

        public static long constructSegment(long seg[],long arr[], int low,int high,int pos)
        {
            if(low==high)
            {
                seg[pos] = arr[low]; 
                return seg[pos];
            }
            int mid = (low+high)/2;
            long t1=constructSegment(seg, arr,low , mid,(2*pos)+1);
            long t2=constructSegment(seg,arr,mid+1,high,(2*pos)+2);
            seg[pos] = t1+t2;
            return seg[pos];

        }
        public static long querySegment(long seg[],int low,int high,int qlow, int qhigh,int pos)
        {
            
            if(qlow<=low&&qhigh>=high)
            {
                return seg[pos];
            }
            else if(qlow>high||qhigh<low )
            {
                return 0;
            }
            else{
                long ans=0;
                int mid=(low+high)/2;
                ans+=querySegment(seg,low , mid, qlow, qhigh,  (2*pos)+1);
                ans+=querySegment(seg, mid+1, high, qlow, qhigh, (2*pos)+2);
            return ans; 
            }

        }
        public static int lcs( char[] X, char[] Y, int m, int n ) 
        { 
            if (m == 0 || n == 0) 
            return 0; 
            if (X[m-1] == Y[n-1]) 
            return 1 + lcs(X, Y, m-1, n-1); 
            else
            return Integer.max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
        } 

        public static long recursion(long start,long end,long cnt[],int a, int b)
        {

            long min=0;
            long count=0;
            int ans1=-1;
            int ans2=-1;
            int l=0;
            int r=cnt.length-1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(cnt[mid]>=start)
                {
                    ans1=mid;
                    r=mid-1;
                }
                else
                {
                    l=mid+1;
                }
            }

            l=0;
            r=cnt.length-1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(cnt[mid]<=end)
                {
                    ans2=mid;
                    l=mid+1;
                }
                else
                {
                    r=mid-1;
                }
            }
            
            if(ans1==-1||ans2==-1||ans2<ans1)
            {
                // System.out.println("min1 "+min);
                min=a;
                return a;

            }
            else
            {
                min=b*(end-start+1)*(ans2-ans1+1);
            }
            if(start==end)
            {
                // System.out.println("min "+min);
                return min;
            }
            long mid = (end+start)/2;
            min = Long.min(min,recursion(start, mid, cnt, a, b)+recursion(mid+1, end, cnt, a, b));
            // System.out.println("min "+min);
            return min;
        }

    



    

        private void solve(InputReader inp, PrintWriter out1) {

           int q = inp.nextInt();
           for(int j=0;j<q;j++)
           {
              int n = inp.nextInt();
              int cnt[] = new int[n];
              int cnt1[] = new int[n];
                for(int i=0;i<n;i++)
                {
                    int x = inp.nextInt();
                    int fi = inp.nextInt();
                    cnt[x-1]++;
                    if(fi==1)
                    {
                        cnt1[x-1]++;
                    }
                }
                int max = Integer.MIN_VALUE;
                for(int i=0;i<n;i++)
                {
                    max = Integer.max(cnt[i], max);
                }
                ArrayList<Integer> arr[] = new ArrayList[max+1];
               
                for(int i=0;i<=max;i++)
                {
                    arr[i]=new ArrayList<>();
                }
                for(int i=0;i<n;i++)
                {
                    arr[cnt[i]].add(cnt1[i]);
                }

                PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
                long sum=0;
                long sum1=0;
                for(int i=max;i>=1;i--)
                {
                    for(int k=0;k<arr[i].size();k++)
                    {
                        pq.add(arr[i].get(k));
                    }
                    if(pq.isEmpty())
                        continue;
                    sum+=i;
                    sum1+=Math.min(i,pq.remove());
                    
                }

                out1.println(sum+" "+sum1);

           }
    }
}





    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

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

        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.valueOf(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}
class  ele implements Comparable<ele>{
    int i;
    int val;
    
    public ele(int i,int val)
    {
        this.val = val;
        this.i=i;
        
    }

    public int compareTo(ele a)
    {
        if(a.val==this.val)
        {
            return Integer.compare(a.i,this.i);
        }
        else
        {
            return Integer.compare(a.val, this.val);
        }
    }
}