#include <bits/stdc++.h>
using namespace std;
struct p {
  int x, y;
};
int a[200001];
int b[200001];
int B[200001];
int c[200001];
bool bz[200001];
p d[200001];
int T, n, i, j, k, l, len, ss;
int h[200001];
long long s, ans, ans2;
bool cmp(p a, p b) { return a.x > b.x; }
void swap(int &x, int &y) {
  int z = x;
  x = y;
  y = z;
}
void put(int s) {
  int i;
  h[++len] = s;
  i = len;
  while (i > 1 && h[i] > h[i / 2]) {
    swap(h[i], h[i / 2]);
    i >>= 1;
  }
}
int get() {
  int S = h[1], i, j;
  h[1] = h[len--];
  i = 1;
  if (i * 2 <= len) j = i * 2;
  if (i * 2 < len && h[j] < h[j + 1]) ++j;
  while (i * 2 <= len && h[i] < h[j]) {
    swap(h[i], h[j]);
    i = j;
    if (i * 2 <= len) j = i * 2;
    if (i * 2 < len && h[j] < h[j + 1]) ++j;
  }
  return S;
}
int main() {
  scanf("%d", &T);
  for (; T; --T) {
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
      scanf("%d%d", &a[i], &c[i]);
      ++b[a[i]];
      B[a[i]] += c[i];
    }
    l = 0;
    for (i = 1; i <= n; i++)
      if (!bz[a[i]]) {
        bz[a[i]] = 1;
        ++l;
        d[l].x = b[a[i]];
        d[l].y = B[a[i]];
      }
    sort(d + 1, d + l + 1, cmp);
    len = 0;
    ans = 0, ans2 = 0, s = d[1].x;
    j = 1;
    put(d[1].y);
    for (i = 1; i <= l; i++) {
      while (j < l && d[j + 1].x >= s) {
        ++j;
        put(d[j].y);
      }
      ans += s;
      ss = get();
      ans2 += (ss < s ? ss : s);
      if (d[i + 1].x < s)
        s = d[i + 1].x;
      else
        --s;
      if (s <= 0) break;
    }
    printf("%I64d %I64d\n", ans, ans2);
    for (i = 1; i <= n; i++) bz[a[i]] = 0, b[a[i]] = 0, B[a[i]] = 0;
  }
}

### Prompt

Your task is to create a CPP solution to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct p {
  int x, y;
};
int a[200001];
int b[200001];
int B[200001];
int c[200001];
bool bz[200001];
p d[200001];
int T, n, i, j, k, l, len, ss;
int h[200001];
long long s, ans, ans2;
bool cmp(p a, p b) { return a.x > b.x; }
void swap(int &x, int &y) {
  int z = x;
  x = y;
  y = z;
}
void put(int s) {
  int i;
  h[++len] = s;
  i = len;
  while (i > 1 && h[i] > h[i / 2]) {
    swap(h[i], h[i / 2]);
    i >>= 1;
  }
}
int get() {
  int S = h[1], i, j;
  h[1] = h[len--];
  i = 1;
  if (i * 2 <= len) j = i * 2;
  if (i * 2 < len && h[j] < h[j + 1]) ++j;
  while (i * 2 <= len && h[i] < h[j]) {
    swap(h[i], h[j]);
    i = j;
    if (i * 2 <= len) j = i * 2;
    if (i * 2 < len && h[j] < h[j + 1]) ++j;
  }
  return S;
}
int main() {
  scanf("%d", &T);
  for (; T; --T) {
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
      scanf("%d%d", &a[i], &c[i]);
      ++b[a[i]];
      B[a[i]] += c[i];
    }
    l = 0;
    for (i = 1; i <= n; i++)
      if (!bz[a[i]]) {
        bz[a[i]] = 1;
        ++l;
        d[l].x = b[a[i]];
        d[l].y = B[a[i]];
      }
    sort(d + 1, d + l + 1, cmp);
    len = 0;
    ans = 0, ans2 = 0, s = d[1].x;
    j = 1;
    put(d[1].y);
    for (i = 1; i <= l; i++) {
      while (j < l && d[j + 1].x >= s) {
        ++j;
        put(d[j].y);
      }
      ans += s;
      ss = get();
      ans2 += (ss < s ? ss : s);
      if (d[i + 1].x < s)
        s = d[i + 1].x;
      else
        --s;
      if (s <= 0) break;
    }
    printf("%I64d %I64d\n", ans, ans2);
    for (i = 1; i <= n; i++) bz[a[i]] = 0, b[a[i]] = 0, B[a[i]] = 0;
  }
}

```