#include <bits/stdc++.h>
using namespace std;
int read() {
  int g = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || '9' < ch) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    g = g * 10 + ch - '0';
    ch = getchar();
  }
  return g * f;
}
const int N = 5e5 + 5;
int vl[N];
struct Seg {
  int mn[N << 2], tag[N << 2];
  void up(int v) { mn[v] = min(mn[v << 1], mn[v << 1 | 1]); }
  void ud(int v, int w) { tag[v] += w, mn[v] += w; }
  void dn(int v) {
    if (tag[v]) ud(v << 1, tag[v]), ud(v << 1 | 1, tag[v]), tag[v] = 0;
  }
  void bu(int v, int l, int r) {
    tag[v] = 0;
    if (l == r) return mn[v] = vl[l], void();
    int mid = l + r >> 1;
    bu(v << 1, l, mid), bu(v << 1 | 1, mid + 1, r);
    up(v);
  }
  void ins(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return ud(v, -1), void();
    int mid = l + r >> 1;
    dn(v);
    if (ql <= mid) ins(v << 1, l, mid, ql, qr);
    if (qr > mid) ins(v << 1 | 1, mid + 1, r, ql, qr);
    up(v);
  }
} seg;
int n, a[N], pre[N], op[N], lmx[N], rmn[N];
void Main() {
  int cnt = 0, col = 0, sign = 0;
  n = read();
  for (int i = (1); i <= (n); i++)
    a[i] = read(), cnt += a[i] ? 0 : 1, pre[i] = pre[i - 1] + (a[i] ? 0 : 1);
  for (int i = (1); i <= (n); i++) lmx[i] = -1, rmn[i] = -1;
  for (int i = (1); i <= (n); i++)
    op[i] = (pre[i] - (a[i] ? 0 : 1) >= (cnt >> 1)) ? 2 : 1;
  for (int i = (1); i <= (n); i++)
    if (a[i] && op[i] == 1) lmx[a[i]] = i;
  for (int i = (n); i >= (1); i--)
    if (a[i] && op[i] == 2) rmn[a[i]] = i;
  for (int i = (1); i <= (n); i++)
    if (lmx[i] != -1 || rmn[i] != -1) col++;
  for (int i = (1); i <= (n); i++)
    if (op[i] == 2 && !a[i]) sign++;
  for (int i = (1); i <= (sign + 1); i++) vl[i] = col + sign + 1 - i;
  int tot = sign + 1;
  seg.bu(1, 1, tot);
  for (int i = (1); i <= (n); i++)
    if (lmx[i] == -1 && rmn[i] != -1)
      seg.ins(1, 1, tot, 1, pre[rmn[i]] + 1 - (cnt >> 1));
  int Ans = min(cnt >> 1, seg.mn[1]);
  int now = 0;
  for (int i = (1); i <= (n); i++)
    if (op[i] == 1) {
      if (!a[i]) now++;
      if (a[i] && i == lmx[a[i]]) {
        int x = rmn[a[i]];
        if (x != -1)
          seg.ins(1, 1, tot, 1, pre[x] + 1 - (cnt >> 1));
        else
          seg.ins(1, 1, tot, 1, tot);
      }
      Ans = min(Ans, seg.mn[1] + now);
    }
  cout << Ans << '\n';
}
signed main() {
  for (int T = read(); T--;) Main();
  return signed();
}
