BerPhone X is almost ready for release with n applications being preinstalled on the phone. A category of an application characterizes a genre or a theme of this application (like "game", "business", or "education"). The categories are given as integers between 1 and n, inclusive; the i-th application has category c_i. 

You can choose m — the number of screens and s — the size of each screen. You need to fit all n icons of the applications (one icon representing one application) meeting the following requirements:

  * On each screen, all the icons must belong to applications of the same category (but different screens can contain icons of applications of the same category); 
  * Each screen must be either completely filled with icons (the number of icons on the screen is equal to s) or almost filled with icons (the number of icons is equal to s-1). 



Your task is to find the minimal possible number of screens m.

Input

The first line contains an integer t (1 ≤ t ≤ 10 000) — the number of test cases in the input. Then t test cases follow.

The first line of each test case contains an integer n (1 ≤ n ≤ 2⋅10^6) — the number of the icons. The second line contains n integers c_1, c_2, ..., c_n (1 ≤ c_i ≤ n), where c_i is the category of the i-th application.

It is guaranteed that the sum of the values of n for all test cases in the input does not exceed 2⋅10^6.

Output

Print t integers — the answers to the given test cases in the order they follow in the input. The answer to a test case is an integer m — the minimum number of screens on which all n icons can be placed satisfying the given requirements.

Example

Input


3
11
1 5 1 5 1 5 1 1 1 1 5
6
1 2 2 2 2 1
5
4 3 3 1 2


Output


3
3
4

Note

In the first test case of the example, all the icons can be placed on three screens of size 4: a screen with 4 icons of the category 1, a screen with 3 icons of the category 1, and a screen with 4 icons of the category 5.
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rang(
    chrono::high_resolution_clock::now().time_since_epoch().count());
long long mpow(long long base, long long exp);
long long power(long long a, long long b);
const long long mod = 998244353;
vector<int> g[300001];
struct node {
  set<int> s;
};
struct segTree {
  long long arr[2001];
  long long res[8003];
  long long pos[8003];
  int idx_mx[8003];
  long long operation_arr[4003];
  long long NO_OPERATION = 0;
  void init(int x, int lo, int hi) {
    operation_arr[x] = NO_OPERATION;
    if (lo == hi) {
      res[x] = arr[lo];
      return;
    }
    int mid = (lo + hi) / 2;
    init(2 * x, lo, mid);
    init(2 * x + 1, mid + 1, hi);
    update(x, lo, hi);
  }
  long long merge_operation(long long a, long long b) { return (a + b); }
  long long merge_results(long long a, long long b) { return min(a, b); }
  void modify(int x, int lo, int hi, int l, int r, long long val) {
    prop(x, lo, hi);
    if (lo >= l && hi <= r) {
      operation_arr[x] = merge_operation(operation_arr[x], val);
      return;
    }
    if (hi < l || lo > r) return;
    int mid = (lo + hi) / 2;
    modify(2 * x, lo, mid, l, r, val);
    modify(2 * x + 1, mid + 1, hi, l, r, val);
    update(x, lo, hi);
  }
  long long get_sum(int x, int lo, int hi, int l, int r) {
    if (lo >= l && hi <= r) return res[x];
    if (lo > r || hi < l) return 0;
    int mid = (lo + hi) / 2;
    return get_sum(2 * x, lo, mid, l, r) +
           get_sum(2 * x + 1, mid + 1, hi, l, r);
  }
  void point_modify(int x, int lo, int hi, int pos, long long val) {
    if (lo == hi) {
      res[x] = val;
      return;
    }
    int mid = (lo + hi) / 2;
    if (pos <= mid)
      point_modify(2 * x, lo, mid, pos, val);
    else
      point_modify(2 * x + 1, mid + 1, hi, pos, val);
    update_point(x);
  }
  long long min_query(int x, int lo, int hi, int l, int r) {
    prop(x, lo, hi);
    if (lo >= l && hi <= r) return merge_operation(res[x], operation_arr[x]);
    int mid = (hi + lo) / 2;
    long long res;
    if (r <= mid)
      res = min_query(2 * x, lo, mid, l, r);
    else if (l > mid)
      res = min_query(2 * x + 1, mid + 1, hi, l, r);
    else
      res =
          min(query(2 * x, lo, mid, l, r), query(2 * x + 1, mid + 1, hi, l, r));
    return res;
  }
  long long get_idx(int x, int lo, int hi, long long v) {
    if (res[x] < v) return hi + 1;
    if (lo == hi) return lo;
    int mid = (lo + hi) / 2;
    if (res[2 * x] >= v)
      return get_idx(2 * x, lo, mid, v);
    else
      return get_idx(2 * x + 1, mid + 1, hi, v);
  }
  void update_point(int x) { res[x] = res[2 * x] + res[2 * x + 1]; }
  long long query(int x, int lo, int hi, int l, int r) {
    prop(x, lo, hi);
    if (lo >= l && hi <= r) {
      return merge_operation(res[x], operation_arr[x]);
    }
    int mid = (hi + lo) / 2;
    long long res;
    if (r <= mid)
      res = query(2 * x, lo, mid, l, r);
    else if (l > mid)
      res = query(2 * x + 1, mid + 1, hi, l, r);
    else
      res = merge_results(query(2 * x, lo, mid, l, r),
                          query(2 * x + 1, mid + 1, hi, l, r));
    return res;
  }
  long long find_pt(int x, int lo, int hi, long long val) {
    if (lo == hi) return lo;
    int mid = (hi + lo) / 2;
    long long m1, m2;
    prop(x, lo, hi);
    m1 = merge_operation(res[2 * x], operation_arr[2 * x]);
    m2 = merge_operation(res[2 * x + 1], operation_arr[2 * x + 1]);
    if (m2 == val)
      return find_pt(2 * x + 1, mid + 1, hi, val);
    else
      return find_pt(2 * x, lo, mid, val);
  }
  int kth_one(int x, int lo, int hi, int k) {
    if (lo == hi) return lo;
    int v1 = res[2 * x];
    int mid = (lo + hi) / 2;
    if (k <= v1)
      return kth_one(2 * x, lo, mid, k);
    else
      return kth_one(2 * x + 1, mid + 1, hi, k - v1);
  }
  long long point_query(int x, int lo, int hi, int p) {
    prop(x, lo, hi);
    if (lo == hi) return operate(res[x], operation_arr[x], lo, lo);
    int mid = (lo + hi) / 2;
    if (p <= mid)
      return point_query(2 * x, lo, mid, p);
    else
      return point_query(2 * x + 1, mid + 1, hi, p);
  }
  void prop(int x, int lo, int hi) {
    if (lo == hi) return;
    operation_arr[2 * x] =
        merge_operation(operation_arr[2 * x], operation_arr[x]);
    operation_arr[2 * x + 1] =
        merge_operation(operation_arr[2 * x + 1], operation_arr[x]);
    operation_arr[x] = NO_OPERATION;
    update(x, lo, hi);
  }
  int operate(int val, int operatr, int l, int r) {
    if (operatr == NO_OPERATION) return NO_OPERATION;
    return val + operatr * (r - l + 1);
  }
  void update(int x, int lo, int hi) {
    if (lo == hi) return;
    res[x] = merge_results(
        merge_operation(res[2 * x], operation_arr[2 * x]),
        merge_operation(res[2 * x + 1], operation_arr[2 * x + 1]));
  }
};
struct FenwickTree {
  int arr[100];
  int n;
  void update(int i, int delta) {
    while (i <= n) {
      arr[i] += delta;
      i = i + (i & (-i));
    }
  }
  int sum(int i) {
    if (i == 0) return 0;
    int res = 0;
    while (i > 0) {
      res = res + arr[i];
      i -= (i & (-i));
    }
    return res;
  }
};
struct dsu {
  int par[1001];
  int size_set[1001];
  void init(int n) {
    for (int i = 0; i <= n; i++) par[i] = i, size_set[i] = 1;
  }
  int get_par(int u) {
    vector<int> temp;
    while (par[u] != u) {
      temp.push_back(u);
      u = par[u];
    }
    for (int i : temp) par[i] = u;
    return u;
  }
  void union_set(int a, int b) {
    a = get_par(a);
    b = get_par(b);
    if (a == b) return;
    if (size_set[a] < size_set[b]) {
      int temp = a;
      a = b;
      b = temp;
    }
    par[b] = a;
    size_set[a] += size_set[b];
  }
  int get_size(int u) {
    u = get_par(u);
    return size_set[u];
  }
};
int check(string s1, string s2) {
  int n1 = s1.size();
  int n2 = s2.size();
  s1 = '$' + s1;
  s2 = '$' + s2;
  int dp[n1 + 1][n2 + 1];
  for (int j = 0; j <= n2; j++) dp[0][j] = 0;
  dp[0][0] = 1;
  for (int i = 1; i <= n1; i++) {
    dp[i][0] = 0;
  }
  int i1 = 1;
  while (i1 <= n1 && s1[i1] == '*') {
    dp[i1][0] = 1;
    i1++;
  }
  int sum[n2 + 1];
  int s = 0;
  for (int i = 0; i <= n2; i++) s = s + dp[0][i], sum[i] = s;
  for (int i = 1; i <= n1; i++) {
    for (int j = 1; j <= n2; j++) {
      char c1 = s1[i];
      char c2 = s2[j];
      if (c1 == '*') {
        if (sum[j] > 0)
          dp[i][j] = 1;
        else
          dp[i][j] = 0;
      } else if (c1 == '?') {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        if (c1 != c2)
          dp[i][j] = 0;
        else
          dp[i][j] = dp[i - 1][j - 1];
      }
    }
    s = 0;
    for (int j = 0; j <= n2; j++) {
      s += dp[i][j];
      sum[j] = s;
    }
  }
  return dp[n1][n2];
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  if (b == 0) return a;
  return gcd(b, a % b);
}
int curr_ans = 0;
map<int, int> coded;
int code2[100001];
bool contains_dup(string s) {
  int cnt[26];
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < s.size(); i++) {
    cnt[s[i] - 'a']++;
    if (cnt[s[i] - 'a'] > 1) return 1;
  }
  return 0;
}
bool isOverflow(long long a, long long b) {
  if (a == 0 || b == 0) return false;
  if (a <= LLONG_MAX / b)
    return false;
  else
    return true;
}
bool isOverflow_add(long long a, long long b) {
  long long res = a + b;
  if (res - a == b && res - b == a) return 0;
  return 1;
}
long long fact(long long i) {
  long long res = 1;
  for (int j = 1; j <= i; j++) res *= j;
  return res;
}
long long f1[5001];
long long f2[5001];
void fct() {
  f1[0] = 1;
  f2[0] = mpow(1, mod - 2);
  for (long long i = 1; i <= 5000; i++) {
    f1[i] = (f1[i - 1] * i) % mod;
    f2[i] = mpow(f1[i], mod - 2);
  }
}
long long ncr(int n, int r) {
  long long res = f1[n];
  res = (res * f2[r]) % mod;
  res = (res * f2[n - r]) % mod;
  return res;
}
int d[10000002];
long long N = (10000000 + 1);
vector<long long> pr;
void seive(int N) {
  for (int i = 2; i < N; i++) d[i] = i;
  for (long long i = 2; i < N; i++) {
    if (d[i] == i) pr.push_back(i);
    for (long long j = 0;
         j < (long long)pr.size() && pr[j] <= d[i] && i * pr[j] < N; j++)
      d[i * pr[j]] = pr[j];
  }
}
bool is_prime(int n) {
  if (d[n] == n) return 1;
  return 0;
}
vector<pair<int, int> > fctorize(int n) {
  vector<pair<int, int> > res;
  while (n > 1) {
    int k = d[n];
    int cnt = 0;
    while (n > 1 && k == d[n]) n /= d[n], cnt++;
    res.push_back({k, cnt});
  }
  return res;
}
int prime_factorize(int n) {
  vector<int> res;
  int tmp = 1;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) res.push_back(n);
  for (int i : res) tmp *= i;
  return tmp;
}
vector<int> get_factors(int n) {
  vector<int> res;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      int f1 = i;
      int f2 = n / i;
      res.push_back(f1);
      if (f1 != f2) res.push_back(f2);
    }
  }
  return res;
}
void solve() {
  int n;
  cin >> n;
  vector<int> a;
  int cnt[n + 1];
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < n; i++) {
    int u;
    cin >> u;
    a.push_back(u);
    cnt[u]++;
  }
  set<int> dist_cnts;
  int mx = -1;
  for (int i = 1; i <= n; i++) {
    dist_cnts.insert(cnt[i]);
    mx = max(mx, cnt[i]);
  }
  mx++;
  int g1[n + 1];
  memset(g1, 0, sizeof(g1));
  int sz = 1;
  for (int j = 1; j <= mx; j++) {
    bool b = 1;
    for (int i : dist_cnts) {
      if (i % j == 0)
        continue;
      else {
        int k = i / j;
        int rem = i - k * j;
        int rem1 = j - rem - 1;
        if (rem1 <= k)
          continue;
        else
          b = 0;
      }
    }
    if (b) sz = j;
  }
  int res = 0;
  for (int i = 1; i <= n; i++) {
    if (cnt[i] > 0) {
      if (cnt[i] % sz == 0)
        res += (cnt[i] / sz);
      else
        res += ((cnt[i] / sz) + 1);
    }
  }
  cout << res << "\n";
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  int t = 1;
  cin >> t;
  int t1 = 1;
  while (t--) {
    solve();
    t1++;
  }
  return 0;
}
long long mpow(long long base, long long exp) {
  base %= mod;
  long long result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((long long)result * base) % mod;
    base = ((long long)base * base) % mod;
    exp >>= 1;
  }
  return result;
}
long long power(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b % 2 == 0) {
      b /= 2;
      if (isOverflow(a, a)) return LLONG_MAX;
      a = a * a;
    } else {
      if (isOverflow(res, a)) return LLONG_MAX;
      res = res * a;
      b--;
    }
  }
  return res;
}
