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 javax.lang.model.type.PrimitiveType;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException{
        new Solver().solve();
    }

    static class Solver {
        void solve() throws IOException{
            Reader reader = new Reader();
            StringBuilder sb = new StringBuilder();
            int Q = reader.nextInt();
            while(Q --> 0) {
                int n = reader.nextInt();
                Pair[] cnt = new Pair[n];
                for(int i = 0; i < n; ++ i) cnt[i] = new Pair();
                for(int i = 0; i < n; ++ i) {
                    int A = reader.nextInt();
                    cnt[A - 1].a ++;
                    cnt[A - 1].b += reader.nextInt();
                }
                Arrays.sort(cnt);
                int tec = cnt[n - 1].a, ans = cnt[n - 1].a, ans0 = 0, idx = n - 1;
                PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
                while(idx >= 0 && cnt[idx].a >= tec) {
                    queue.add(cnt[idx].b);
                    -- idx;
                }
                ans0 += Math.min(queue.element(), tec);
                queue.remove();
                for(int i = n - 2; i >= 0; -- i) {
                    tec = Math.min(tec - 1, cnt[i].a);
                    if(tec <= 0) break;
                    ans += tec;
                    while(idx >= 0 && cnt[idx].a >= tec) {
                        queue.add(cnt[idx].b);
                        -- idx;
                    }
                    ans0 += Math.min(queue.element(), tec);
                    queue.remove();
                }
                sb.append(ans).append(' ').append(ans0).append('\n');
            }
            System.out.println(sb);
        }

        class Pair implements Comparable<Pair> {
            int a = 0, b = 0;

            Pair() {}

            Pair(int a, int b) {
                this.a = a;
                this.b = b;
            }

            @Override
            public int compareTo(Pair o) {
                return a - o.a;
            }
        }
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
        public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public Reader(String file_name) throws IOException {din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
        }public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
        }public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
        }public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
        }public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
        }private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
        }private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
        }public void close() throws IOException{if(din==null) return;din.close();}
    }
}