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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long OO = (long long)(4e18) + 9;
const long long MOD = (long long)(1e9) + 7;
const int oo = 2147483647;
const double EPS = 1e-8;
const double PI = acos(-1.0);
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
string abc = "abcdefghijklmnopqrstuvwxyz";
string vowels = "aeiouy";
template <typename X, typename Y>
bool ckmin(X& a, Y b) {
  return a > b ? a = b, true : false;
}
template <typename X, typename Y>
bool ckmax(X& a, Y b) {
  return a < b ? a = b, true : false;
}
bool ckcmp(string& a, string b) {
  if (b == "") return false;
  if (a == "") return a = b, true;
  if ((int)b.size() < (int)a.size()) return a = b, true;
  if ((int)a.size() < (int)b.size()) return false;
  if (a < b) return false;
  return a = b, true;
}
int dcmp(long double d1, long double d2) {
  return fabs(d1 - d2) <= EPS ? 0 : d1 > d2 ? 1 : -1;
}
long long gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
long long lcm(long long a, long long b) { return a * (b / gcd(a, b)); }
int conv_2_1(int r, int c, int nCol) { return (nCol * r) + c + 1; }
pair<int, int> conv_1_2(int n, int nCol) {
  int r = n / nCol, c = n % nCol;
  return pair<int, int>(r, c);
}
void inter(string second) {
  cout << second << endl;
  fflush(stdout);
}
struct mi {
  long long v;
  explicit operator long long() const { return v; }
  mi() { v = 0; }
  mi(long long _v) {
    v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
    if (v < 0) v += MOD;
  }
  friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
  mi& operator+=(const mi& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    v = v * m.v % MOD;
    return *this;
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  mi operator-() const { return mi(-v); }
  mi& operator++() { return *this += 1; }
  mi& operator--() { return *this -= 1; }
  mi operator++(int) {
    mi temp;
    temp.v = v++;
    return temp;
  }
  mi operator--(int) {
    mi temp;
    temp.v = v--;
    return temp;
  }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
  friend ostream& operator<<(ostream& os, const mi& m) {
    os << m.v;
    return os;
  }
  friend istream& operator>>(istream& is, mi& m) {
    long long x;
    is >> x;
    m.v = x;
    return is;
  }
};
const int NN = 1e5 + 10;
mi fact[NN];
mi facInv[NN];
void init() {
  fact[0] = facInv[0] = 1;
  for (int i = 1; i < NN; ++i)
    fact[i] = (fact[i - 1] * 1LL * i), facInv[i] = inv(fact[i]);
}
mi nCr(mi n, mi r) {
  long long a = (long long)n, b = (long long)r;
  if (b > a or a < 0 or b < 0) return 0;
  return fact[a] * facInv[b] * facInv[a - b];
}
int main() {
  int t = 1;
  cin >> t;
  while (t--) {
    int x, n, fi;
    cin >> n;
    vector<pair<int, int>> cnt(n + 1);
    for (int i = 0; i < n; i++) {
      cin >> x >> fi;
      if (fi) cnt[x].second++;
      cnt[x].first++;
    }
    set<pair<pair<int, int>, int>> st;
    for (int i = 0; i < n + 1; i++)
      if (cnt[i].first) st.insert({{-cnt[i].first, -cnt[i].second}, i});
    auto it = st.begin();
    int ans1 = -(it->first.first), ans2 = -(it->first.second),
        last = it->first.first;
    st.erase(it);
    pair<pair<int, int>, int> p;
    while (last and (int) st.size()) {
      it = st.begin();
      while (it->first.first <= last)
        p = {{last + 1, it->first.second}, it->second}, st.erase(it),
        st.insert(p), it = st.begin();
      if (not(it->first.first)) break;
      ans1 += -(it->first.first),
          ans2 += min(-(it->first.second), -(it->first.first)),
          last = it->first.first;
      st.erase(it);
    }
    cout << ans1 << ' ' << ans2 << endl;
  }
  return 0;
}