#include <bits/stdc++.h>
using namespace std;
int t;
int n, n_2;
int a[300233];
int cnt, ans;
int p1[300233], p2[300233];
int f[300233];
int main() {
  cin >> t;
  while (t--) {
    scanf("%d", &n);
    cnt = 0;
    memset(p1 + 1, 0, n * 4);
    memset(f + 1, 0, n * 4);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      if (!p1[a[i]]) p1[a[i]] = i;
      p2[a[i]] = i;
    }
    sort(a + 1, a + 1 + n);
    n_2 = unique(a + 1, a + 1 + n) - a - 1;
    for (int i = 1; i <= n_2; i++) {
      if (p1[a[i]] > p2[a[i - 1]])
        f[a[i]] = f[a[i - 1]] + 1;
      else
        f[a[i]] = 1;
      cnt = max(cnt, f[a[i]]);
    }
    ans = n_2 - cnt;
    printf("%d\n", ans);
  }
  return 0;
}
