#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int t, n, m, lmx, rmi, ans, a[N], s[N], l[N], r[N];
bool use[N];
struct data {
  int x, y, z;
  bool operator<(const data &n) const {
    if (x != n.x) {
      return x < n.x;
    }
    if (y != n.y) {
      return y < n.y;
    }
    return z < n.z;
  }
} tmp, p[N];
set<data> minn;
bool cmp1(data a, data b) { return a.y < b.y; }
bool cmp2(data a, data b) { return a.x > b.x; }
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      s[i] = s[i - 1] + (!a[i]);
    }
    lmx = s[n] / 2;
    rmi = (s[n] + 3) / 2;
    for (int i = 1; i <= n; i++) {
      l[i] = 0;
      r[i] = n + 1;
      use[i] = false;
    }
    for (int i = 1; i <= n; i++) {
      if (a[i]) {
        if (s[i] >= lmx) {
          r[a[i]] = min(r[a[i]], max(rmi, s[i] + 1));
        }
        if (s[n] - s[i] >= lmx) {
          l[a[i]] = max(l[a[i]], min(lmx, s[i]));
        }
      }
    }
    m = 0;
    for (int i = 1; i <= n; i++) {
      if (l[i] != 0 || r[i] != n + 1) {
        p[++m] = (data){l[i], r[i], i};
      }
    }
    ans = 0;
    minn.clear();
    sort(p + 1, p + m + 1, cmp1);
    for (int i = rmi, j = 0; i <= s[n]; i++) {
      while (j < m && p[j + 1].y == i) {
        j++;
        minn.insert(p[j]);
      }
      if (minn.size()) {
        tmp = *minn.begin();
        minn.erase(tmp);
        use[tmp.z] = true;
        ans++;
      }
    }
    sort(p + 1, p + m + 1, cmp2);
    for (int i = lmx, j = 0, k = 0; i >= 1; i--) {
      while (j < m && p[j + 1].x == i) {
        j++;
        if (!use[p[j].z]) {
          k++;
        }
      }
      if (k) {
        ans++;
        k--;
      }
    }
    ans = min(ans, lmx);
    printf("%d\n", ans);
  }
  return 0;
}
