#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int MAXN = 300001;
const long long INF = 1000000000ll;
const long long LLINF = 1000000000000000000ll;
const int MOD = 1000000007;
int a[MAXN];
int mx[MAXN];
int l[MAXN];
int r[MAXN];
int pr[MAXN];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.precision(10);
  cout << fixed;
  int t;
  cin >> t;
  for (int tt = 0; tt < (int)(t); tt++) {
    int n;
    cin >> n;
    for (int i = 0; i < (int)(n); i++) {
      l[i] = r[i] = -1;
    }
    int cnt = 0;
    for (int i = 0; i < (int)(n); i++) {
      cin >> a[i];
      a[i]--;
      if (l[a[i]] == -1) {
        l[a[i]] = i;
        cnt++;
      }
      r[a[i]] = i;
    }
    int prev = -1;
    for (int i = 0; i < (int)(n); i++) {
      if (l[i] != -1) {
        pr[i] = prev;
        prev = i;
      }
    }
    int res = 0;
    for (int i = 0; i < (int)(n); i++) {
      if (l[a[i]] == i) {
        mx[i] = 1;
        if (pr[a[i]] != -1 && r[pr[a[i]]] < i) {
          mx[i] = 1 + mx[l[pr[a[i]]]];
        }
        res = max(res, mx[i]);
      }
    }
    cout << cnt - res << "\n";
  }
  return 0;
}
