#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn];
int f[maxn];
struct node {
  int type;
  int like;
  int cnt;
} b[maxn];
set<int> s;
int n, tot;
void init() {
  s.clear();
  tot = 0;
}
bool cmp1(node x, node y) {
  return x.cnt == y.cnt ? (x.like > y.like) : (x.cnt > y.cnt);
}
bool cmp2(node x, node y) {
  return x.like == y.like ? (x.cnt > y.cnt) : (x.like > y.like);
}
vector<int> kindex;
int main() {
  int q;
  scanf("%d", &q);
  memset(f, 0, sizeof(f));
  while (q--) {
    scanf("%d", &n);
    init();
    kindex.clear();
    for (int i = 0, tmp; i < n; i++) {
      scanf("%d%d", &a[i], &tmp);
      f[a[i]] += tmp;
      kindex.push_back(a[i]);
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++)
      if (i == 0 || a[i] > a[i - 1]) {
        b[tot].cnt = 1;
        b[tot].like = f[a[i]];
        b[tot++].type = a[i];
      } else {
        b[tot - 1].cnt++;
      }
    sort(b, b + tot, cmp1);
    int ans1 = 0, ans2 = 0, cur;
    for (int i = 0; i < tot; i++) {
      if (i == 0) {
        ans1 += b[0].cnt;
        cur = b[0].cnt;
      } else {
        if (b[i].cnt >= cur && cur >= 1) {
          ans1 += (cur - 1);
          cur--;
        } else {
          ans1 += b[i].cnt;
          cur = b[i].cnt;
        }
      }
      if (cur == 0) break;
      s.insert(-cur);
    }
    sort(b, b + tot, cmp2);
    for (int i = 0; i < tot && !s.empty(); i++) {
      set<int>::iterator it = s.lower_bound(-b[i].cnt);
      if (it == s.end()) continue;
      ans2 += min(b[i].like, -(*it));
      s.erase(it);
    }
    cout << ans1 << " " << ans2 << endl;
    int ins = kindex.size();
    for (int i = 0; i < ins; i++) {
      f[kindex[i]] = 0;
    }
  }
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn];
int f[maxn];
struct node {
  int type;
  int like;
  int cnt;
} b[maxn];
set<int> s;
int n, tot;
void init() {
  s.clear();
  tot = 0;
}
bool cmp1(node x, node y) {
  return x.cnt == y.cnt ? (x.like > y.like) : (x.cnt > y.cnt);
}
bool cmp2(node x, node y) {
  return x.like == y.like ? (x.cnt > y.cnt) : (x.like > y.like);
}
vector<int> kindex;
int main() {
  int q;
  scanf("%d", &q);
  memset(f, 0, sizeof(f));
  while (q--) {
    scanf("%d", &n);
    init();
    kindex.clear();
    for (int i = 0, tmp; i < n; i++) {
      scanf("%d%d", &a[i], &tmp);
      f[a[i]] += tmp;
      kindex.push_back(a[i]);
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++)
      if (i == 0 || a[i] > a[i - 1]) {
        b[tot].cnt = 1;
        b[tot].like = f[a[i]];
        b[tot++].type = a[i];
      } else {
        b[tot - 1].cnt++;
      }
    sort(b, b + tot, cmp1);
    int ans1 = 0, ans2 = 0, cur;
    for (int i = 0; i < tot; i++) {
      if (i == 0) {
        ans1 += b[0].cnt;
        cur = b[0].cnt;
      } else {
        if (b[i].cnt >= cur && cur >= 1) {
          ans1 += (cur - 1);
          cur--;
        } else {
          ans1 += b[i].cnt;
          cur = b[i].cnt;
        }
      }
      if (cur == 0) break;
      s.insert(-cur);
    }
    sort(b, b + tot, cmp2);
    for (int i = 0; i < tot && !s.empty(); i++) {
      set<int>::iterator it = s.lower_bound(-b[i].cnt);
      if (it == s.end()) continue;
      ans2 += min(b[i].like, -(*it));
      s.erase(it);
    }
    cout << ans1 << " " << ans2 << endl;
    int ins = kindex.size();
    for (int i = 0; i < ins; i++) {
      f[kindex[i]] = 0;
    }
  }
  return 0;
}

```