#include <bits/stdc++.h>
using namespace std;
template <class t>
inline t read(t &x) {
  x = 0;
  char c = getchar();
  bool f = 0;
  while (!isdigit(c)) f |= c == '-', c = getchar();
  while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  if (f) x = -x;
  return x;
}
template <class t>
inline void write(t x) {
  if (x < 0) {
    putchar('-');
    write(-x);
  } else {
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
  }
}
const int N = 3e5 + 5;
int q, n, a[N], l[N], r[N], b[N];
void doit() {
  read(n);
  for (int i = 1; i <= n; i++) l[i] = n + 1, r[i] = 0;
  for (int i = 1; i <= n; i++)
    read(a[i]), l[a[i]] = min(l[a[i]], i), r[a[i]] = max(r[a[i]], i),
                b[i] = a[i];
  sort(b + 1, b + 1 + n);
  int un = unique(b + 1, b + 1 + n) - b - 1, ans = 1, now = 1;
  for (int i = 2; i <= un; i++)
    if (l[b[i]] > r[b[i - 1]])
      now++, ans = max(ans, now);
    else
      now = 1;
  write(un - ans);
  puts("");
}
signed main() {
  read(q);
  while (q--) doit();
}
