#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
long long n, a[300005], l[300005], r[300005];
bool vis[300005];
void work() {
  n = read();
  for (register long long i = (1); i <= (n); ++i) a[i] = read(), vis[i] = 0;
  long long all = 0, now = 0, mx = 0;
  for (register long long i = (1); i <= (n); ++i) {
    if (!vis[a[i]]) vis[a[i]] = 1, l[a[i]] = i, ++all;
    r[a[i]] = i;
  }
  long long lst = -1;
  for (register long long i = (1); i <= (n); ++i)
    if (vis[i]) {
      if (!now)
        now = mx = 1, lst = i;
      else {
        if (l[i] > r[lst])
          now++;
        else
          now = 1;
        lst = i;
        mx = max(mx, now);
      }
    }
  cout << all - mx << endl;
}
signed main() {
  long long T = read();
  while (T--) work();
  return 0;
}
