#include <bits/stdc++.h>
const int N = 333333;
using namespace std;
int a[N], f[N], d[N], r[N], s[N];
int g, z;
bool used[N];
int main() {
  int q, n;
  scanf("%d", &q);
  while (q--) {
    scanf("%d", &n);
    z = g = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      r[i] = 0;
      s[i] = 0;
      d[i] = 0;
      f[i] = 0;
      used[i] = false;
    }
    for (int i = n; i >= 1; i--) {
      f[a[i]] = i;
    }
    for (int i = n - 1; i >= 1; i--) {
      if (f[i + 1])
        d[i] = i + 1;
      else
        d[i] = d[i + 1];
    }
    for (int i = n; i >= 1; i--) {
      if (!used[a[i]]) {
        used[a[i]] = true;
        ++z;
        r[a[i]] = s[d[a[i]]] + 1;
      }
      if (i == f[a[i]]) {
        s[a[i]] = r[a[i]];
      }
      if (g < r[a[i]]) g = r[a[i]];
    }
    printf("%d\n", z - g);
  }
}
