#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    int n;
    cin >> n;
    int a[n], b[n];
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      b[i] = a[i];
    }
    sort(b, b + n);
    int prev[n + 1];
    fill(prev, prev + n + 1, -1);
    for (int i = 1; i < n; ++i) {
      if (prev[b[i]] == -1) prev[b[i]] = b[i - 1];
    }
    int first[n + 1], last[n + 1];
    fill(first, first + n + 1, 1e9);
    fill(last, last + n + 1, -1);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (first[a[i]] == 1e9) cnt++;
      first[a[i]] = min(first[a[i]], i);
      last[a[i]] = max(last[a[i]], i);
    }
    int dp[n + 1];
    fill(dp, dp + n + 1, 1);
    for (int i = 1; i < n + 1; ++i) {
      int p = prev[i];
      if (p == -1 || p == i) continue;
      if (last[p] < first[i]) dp[i] = max(dp[i], dp[p] + 1);
    }
    int ma = 0;
    for (int i = 0; i < n + 1; ++i) {
      ma = max(ma, dp[i]);
    }
    cout << cnt - ma << endl;
  }
}
