#include <bits/stdc++.h>
#pragma GCC optimize("2,Ofast,inline")
const long long N = 6e5 + 10;
const long long mod = 1e9 + 7;
const long long inf = 0x3f3f3f;
const double eps = 1e-9;
using namespace std;
template <typename tp>
inline void read(tp &x) {
  x = 0;
  char c = getchar();
  bool f = 0;
  for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar())
    ;
  if (f) x = -x;
}
long long T, n, x[N], maxn[N], minn[N], la[N];
long long vis[N], num, ans, last, anss[N];
void init() {
  num = ans = 0;
  for (long long i = 1; i <= n; i++) {
    vis[i] = 0;
    maxn[i] = 0;
    minn[i] = inf;
  }
}
signed main() {
  read(T);
  for (long long cas = 1; cas <= T; cas++) {
    read(n);
    init();
    for (long long i = 1; i <= n; i++) {
      read(x[i]);
      if (!vis[x[i]]) num++;
      vis[x[i]] = 1;
    }
    for (long long i = 1; i <= n; i++)
      minn[x[i]] = min(minn[x[i]], i), maxn[x[i]] = max(maxn[x[i]], i);
    long long last = -1;
    for (long long i = 1; i <= n; i++)
      if (vis[i]) la[i] = last, last = i;
    for (long long i = 1; i <= n; i++)
      if (vis[i]) {
        long long zz = 0;
        if (la[i] != -1 && maxn[la[i]] < minn[i]) zz = anss[la[i]];
        anss[i] = zz + 1;
        ans = max(ans, anss[i]);
      }
    printf("%lld\n", (num - ans));
  }
  return 0;
}
