#include <bits/stdc++.h>
using namespace std;
int a[500000], ll[500001], rr[500001];
vector<pair<int, int> > v;
priority_queue<int, vector<int>, greater<int> > H;
int main() {
  int i;
  int t, n;
  scanf("%d", &t);
  while (t--) {
    int z = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", &a[i]), z += (a[i] == 0);
    int l = 0, r = n / 3;
    while (l < r) {
      int m = (l + r + 1) / 2;
      if (2 * m > z)
        r = m - 1;
      else {
        int p = 0;
        fill(ll, ll + n + 1, 0), fill(rr, rr + n + 1, 0);
        for (i = 0; i < n; i++) {
          if (a[i] != 0) {
            if (p <= m)
              ll[a[i]] = max(ll[a[i]], p);
            else
              rr[a[i]] = max(rr[a[i]], min(z - p, m));
          } else
            p++;
        }
        for (i = 1; i <= n; i++) {
          if (ll[i] + rr[i] >= m) ll[i] = m, rr[i] = 0;
          if (ll[i] + rr[i] > 0) v.push_back(make_pair(ll[i], rr[i]));
        }
        int j = 0;
        sort(v.begin(), v.end());
        for (i = 0; i < m; i++) {
          while ((j < v.size()) && (v[j].first <= i)) j++;
          if (j >= v.size())
            break;
          else
            j++;
        }
        if (i == m)
          l = m;
        else {
          int p = i;
          j = v.size() - 1;
          for (i = p - 1; i >= 0; i--) {
            while ((j >= 0) && (v[j].first > i)) H.push(v[j].second), j--;
            H.pop();
          }
          while (j >= 0) H.push(v[j].second), j--;
          for (i = 0; i < m - p; i++) {
            while (!H.empty() && (H.top() <= i)) H.pop();
            if (H.empty())
              break;
            else
              H.pop();
          }
          if (i < m - p)
            r = m - 1;
          else
            l = m;
        }
        v.clear();
        while (!H.empty()) H.pop();
      }
    }
    printf("%d\n", l);
  }
  return 0;
}
