#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using ull = unsigned long long int;
template <typename Arg1>
void debug_out(const char* name, Arg1&& arg1) {
  cerr << name << " = " << arg1 << " ]"
       << "\n";
}
template <typename Arg1, typename... Args>
void debug_out(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << ",";
  debug_out(comma + 1, args...);
}
constexpr long long inf = 2e9, ninf = -2e9;
constexpr long double eps = 1e-9;
constexpr long double pi = 3.141592653589793238;
constexpr long long mod = 1e9 + 7;
constexpr long long N = 3e5 + 5, M = 2e5 + 5;
namespace BSSTL {
template <typename T1, typename T2>
long long upBoundInd(T1 left, T1 right, T2 key) {
  long long ind = upper_bound(left, right, key) - left + 1;
  return ind;
}
template <typename T1, typename T2>
long long lowBoundInd(T1 left, T1 right, T2 key) {
  long long ind = lower_bound(left, right, key) - left + 1;
  return ind;
}
template <typename T1, typename T2>
long long cntBigger(T1 left, T1 right, T2 key) {
  long long cnt = right - upper_bound(left, right, key);
  return cnt;
}
template <typename T1, typename T2>
long long cntSmaller(T1 left, T1 right, T2 key) {
  long long cnt = lower_bound(left, right, key) - left;
  return cnt;
}
};  // namespace BSSTL
using namespace BSSTL;
long long n, m;
long long freq[N][2];
array<long long, 2> cnt[N];
class SegmentTree {
 public:
  vector<long long> segTree;
  long long base = 0;
  SegmentTree() {
    segTree.resize(4 * n);
    buildSegTree(1, 1, n);
  }
  long long join(long long a, long long b) {
    if (a == 0) return b;
    if (b == 0) return a;
    if (max(cnt[a][1], cnt[b][1]) == cnt[a][1])
      return a;
    else
      return b;
  }
  void buildSegTree(long long node, long long start, long long end) {
    if (start == end)
      segTree[node] = start;
    else {
      long long mid = start + ((end - start) / 2);
      buildSegTree(2 * node, start, mid);
      buildSegTree(2 * node + 1, mid + 1, end);
      segTree[node] = join(segTree[2 * node], segTree[2 * node + 1]);
    }
  }
  void printSegTree() {
    for (auto x : segTree) cout << x << ' ';
    cout << '\n';
  }
  long long query(long long node, long long start, long long end,
                  const long long& left, const long long& right) {
    if (start >= left && end <= right)
      return segTree[node];
    else if (end < left || start > right)
      return base;
    else {
      long long mid = start + ((end - start) / 2);
      return join(query(2 * node, start, mid, left, right),
                  query(2 * node + 1, mid + 1, end, left, right));
    }
  }
  void valueUpdate(long long node, long long start, long long end,
                   const long long& index, const long long& value) {
    if (start == index && end == index)
      cnt[index][1] = 0;
    else {
      long long mid = start + ((end - start) / 2);
      if (index <= mid)
        valueUpdate(2 * node, start, mid, index, value);
      else
        valueUpdate(2 * node + 1, mid + 1, end, index, value);
      segTree[node] = join(segTree[2 * node], segTree[2 * node + 1]);
    }
  }
};
void DONT_ASSUME_BLINDLY() {
  cin >> n;
  for (long long i = (1); i <= (n); ++i)
    for (long long j = (0); j <= (1); ++j) freq[i][j] = 0;
  for (long long i = (1); i <= (n); ++i) {
    long long val, f;
    cin >> val >> f;
    freq[val][f]++;
  }
  m = 0;
  for (long long i = (1); i <= (n); ++i) {
    if (freq[i][0] || freq[i][1]) {
      cnt[++m] = {freq[i][0] + freq[i][1], freq[i][1]};
    }
  }
  swap(n, m);
  sort(cnt + 1, cnt + n + 1);
  vector<long long> take;
  long long mx = inf;
  for (long long i = (n); i >= (1); --i) {
    mx = min(mx - 1, cnt[i][0]);
    if (mx <= 0) break;
    take.push_back(mx);
  }
  SegmentTree sgt;
  long long ans1 = accumulate((take).begin(), (take).end(), 0ll), ans2 = 0;
  for (auto& it : take) {
    long long ind =
        lowBoundInd(cnt + 1, cnt + n + 1, array<long long, 2>{it, 0});
    assert(ind >= 1 && ind <= n);
    long long mx_ind = sgt.query(1, 1, n, ind, n);
    ans2 += min(it, cnt[mx_ind][1]);
    sgt.valueUpdate(1, 1, n, mx_ind, 0);
  }
  cout << ans1 << ' ' << ans2 << '\n';
}
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  long long tc = 1;
  cin >> tc;
  for (long long i = 1; i <= tc; i++) {
    DONT_ASSUME_BLINDLY();
  }
  cerr << "[time:" << 1.0 * clock() / CLOCKS_PER_SEC << "s] ";
  return 0;
}

### Prompt

Please provide a CPP coded solution 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;
using ll = long long int;
using ld = long double;
using ull = unsigned long long int;
template <typename Arg1>
void debug_out(const char* name, Arg1&& arg1) {
  cerr << name << " = " << arg1 << " ]"
       << "\n";
}
template <typename Arg1, typename... Args>
void debug_out(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << ",";
  debug_out(comma + 1, args...);
}
constexpr long long inf = 2e9, ninf = -2e9;
constexpr long double eps = 1e-9;
constexpr long double pi = 3.141592653589793238;
constexpr long long mod = 1e9 + 7;
constexpr long long N = 3e5 + 5, M = 2e5 + 5;
namespace BSSTL {
template <typename T1, typename T2>
long long upBoundInd(T1 left, T1 right, T2 key) {
  long long ind = upper_bound(left, right, key) - left + 1;
  return ind;
}
template <typename T1, typename T2>
long long lowBoundInd(T1 left, T1 right, T2 key) {
  long long ind = lower_bound(left, right, key) - left + 1;
  return ind;
}
template <typename T1, typename T2>
long long cntBigger(T1 left, T1 right, T2 key) {
  long long cnt = right - upper_bound(left, right, key);
  return cnt;
}
template <typename T1, typename T2>
long long cntSmaller(T1 left, T1 right, T2 key) {
  long long cnt = lower_bound(left, right, key) - left;
  return cnt;
}
};  // namespace BSSTL
using namespace BSSTL;
long long n, m;
long long freq[N][2];
array<long long, 2> cnt[N];
class SegmentTree {
 public:
  vector<long long> segTree;
  long long base = 0;
  SegmentTree() {
    segTree.resize(4 * n);
    buildSegTree(1, 1, n);
  }
  long long join(long long a, long long b) {
    if (a == 0) return b;
    if (b == 0) return a;
    if (max(cnt[a][1], cnt[b][1]) == cnt[a][1])
      return a;
    else
      return b;
  }
  void buildSegTree(long long node, long long start, long long end) {
    if (start == end)
      segTree[node] = start;
    else {
      long long mid = start + ((end - start) / 2);
      buildSegTree(2 * node, start, mid);
      buildSegTree(2 * node + 1, mid + 1, end);
      segTree[node] = join(segTree[2 * node], segTree[2 * node + 1]);
    }
  }
  void printSegTree() {
    for (auto x : segTree) cout << x << ' ';
    cout << '\n';
  }
  long long query(long long node, long long start, long long end,
                  const long long& left, const long long& right) {
    if (start >= left && end <= right)
      return segTree[node];
    else if (end < left || start > right)
      return base;
    else {
      long long mid = start + ((end - start) / 2);
      return join(query(2 * node, start, mid, left, right),
                  query(2 * node + 1, mid + 1, end, left, right));
    }
  }
  void valueUpdate(long long node, long long start, long long end,
                   const long long& index, const long long& value) {
    if (start == index && end == index)
      cnt[index][1] = 0;
    else {
      long long mid = start + ((end - start) / 2);
      if (index <= mid)
        valueUpdate(2 * node, start, mid, index, value);
      else
        valueUpdate(2 * node + 1, mid + 1, end, index, value);
      segTree[node] = join(segTree[2 * node], segTree[2 * node + 1]);
    }
  }
};
void DONT_ASSUME_BLINDLY() {
  cin >> n;
  for (long long i = (1); i <= (n); ++i)
    for (long long j = (0); j <= (1); ++j) freq[i][j] = 0;
  for (long long i = (1); i <= (n); ++i) {
    long long val, f;
    cin >> val >> f;
    freq[val][f]++;
  }
  m = 0;
  for (long long i = (1); i <= (n); ++i) {
    if (freq[i][0] || freq[i][1]) {
      cnt[++m] = {freq[i][0] + freq[i][1], freq[i][1]};
    }
  }
  swap(n, m);
  sort(cnt + 1, cnt + n + 1);
  vector<long long> take;
  long long mx = inf;
  for (long long i = (n); i >= (1); --i) {
    mx = min(mx - 1, cnt[i][0]);
    if (mx <= 0) break;
    take.push_back(mx);
  }
  SegmentTree sgt;
  long long ans1 = accumulate((take).begin(), (take).end(), 0ll), ans2 = 0;
  for (auto& it : take) {
    long long ind =
        lowBoundInd(cnt + 1, cnt + n + 1, array<long long, 2>{it, 0});
    assert(ind >= 1 && ind <= n);
    long long mx_ind = sgt.query(1, 1, n, ind, n);
    ans2 += min(it, cnt[mx_ind][1]);
    sgt.valueUpdate(1, 1, n, mx_ind, 0);
  }
  cout << ans1 << ' ' << ans2 << '\n';
}
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  long long tc = 1;
  cin >> tc;
  for (long long i = 1; i <= tc; i++) {
    DONT_ASSUME_BLINDLY();
  }
  cerr << "[time:" << 1.0 * clock() / CLOCKS_PER_SEC << "s] ";
  return 0;
}

```