#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("trapv")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
const int N = 1e3 + 40;
const int MAXK = 12;
const long long int INF = 1000000000000000000;
const int RANDOM =
    chrono::high_resolution_clock::now().time_since_epoch().count();
long long int expo_pow(long long int x, long long int y) {
  if (y == 0) return 1;
  y = y % ((1000000007) - 1);
  x %= (1000000007);
  if (y == 0) y = (1000000007) - 1;
  long long int res = 1;
  while (y) {
    if (y & 1) res = (res * x) % (1000000007);
    x = (x * x) % (1000000007);
    y >>= 1;
  }
  return res;
}
long long int modInverse(long long int a, long long int m = (1000000007)) {
  return expo_pow(a, m - 2);
}
void solve() {
  int n;
  cin >> n;
  vector<vector<long long int>> cnt(n + 2);
  map<int, int> ones;
  map<int, int> t;
  for (long long int i = (1); i < (n + 1); i++) {
    int tp, w;
    cin >> tp >> w;
    if (w) ones[tp]++;
    t[tp]++;
  }
  for (auto x : t) {
    cnt[x.second].push_back(ones[x.first]);
  }
  priority_queue<pair<long long int, long long int>> pq;
  long long int ans = 0;
  long long int fo = 0;
  set<long long int> second;
  for (long long int i = (1); i < (n + 1); i++) {
    if (1) second.insert(i);
    for (long long int j = (0); j < (cnt[i].size()); j++) {
      pq.push(make_pair(cnt[i][j], i));
    }
  }
  while (second.size()) {
    if (pq.empty()) break;
    int x = pq.top().second;
    auto it = second.upper_bound(x);
    if (it == second.begin()) {
      pq.pop();
      continue;
    }
    it--;
    ans += *it;
    fo += min(*it, pq.top().first);
    pq.pop();
    second.erase(*it);
  }
  cout << ans << " " << fo << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
}

### Prompt

Please formulate 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;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("trapv")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
const int N = 1e3 + 40;
const int MAXK = 12;
const long long int INF = 1000000000000000000;
const int RANDOM =
    chrono::high_resolution_clock::now().time_since_epoch().count();
long long int expo_pow(long long int x, long long int y) {
  if (y == 0) return 1;
  y = y % ((1000000007) - 1);
  x %= (1000000007);
  if (y == 0) y = (1000000007) - 1;
  long long int res = 1;
  while (y) {
    if (y & 1) res = (res * x) % (1000000007);
    x = (x * x) % (1000000007);
    y >>= 1;
  }
  return res;
}
long long int modInverse(long long int a, long long int m = (1000000007)) {
  return expo_pow(a, m - 2);
}
void solve() {
  int n;
  cin >> n;
  vector<vector<long long int>> cnt(n + 2);
  map<int, int> ones;
  map<int, int> t;
  for (long long int i = (1); i < (n + 1); i++) {
    int tp, w;
    cin >> tp >> w;
    if (w) ones[tp]++;
    t[tp]++;
  }
  for (auto x : t) {
    cnt[x.second].push_back(ones[x.first]);
  }
  priority_queue<pair<long long int, long long int>> pq;
  long long int ans = 0;
  long long int fo = 0;
  set<long long int> second;
  for (long long int i = (1); i < (n + 1); i++) {
    if (1) second.insert(i);
    for (long long int j = (0); j < (cnt[i].size()); j++) {
      pq.push(make_pair(cnt[i][j], i));
    }
  }
  while (second.size()) {
    if (pq.empty()) break;
    int x = pq.top().second;
    auto it = second.upper_bound(x);
    if (it == second.begin()) {
      pq.pop();
      continue;
    }
    it--;
    ans += *it;
    fo += min(*it, pq.top().first);
    pq.pop();
    second.erase(*it);
  }
  cout << ans << " " << fo << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
}

```