#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  set<int> seen;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
    seen.insert(a[i]);
  }
  vector<int> ids(seen.begin(), seen.end());
  map<int, int> remap;
  for (int i = 0; i < ids.size(); ++i) {
    remap[ids[i]] = i;
  }
  for (int i = 0; i < n; ++i) {
    a[i] = remap[a[i]];
  }
  int tot = seen.size();
  vector<int> nxt(tot, -1);
  vector<int> l(tot, n);
  vector<int> r(tot, -1);
  for (int i = 0; i < n; ++i) {
    l[a[i]] = min(l[a[i]], i);
    r[a[i]] = max(r[a[i]], i);
  }
  int longest = 1;
  for (int i = 0; i < tot;) {
    int cur = i;
    int cr = -1;
    while (cur < tot && l[cur] > cr) {
      cr = r[cur];
      ++cur;
    }
    longest = max(longest, cur - i);
    i = cur;
  }
  cout << tot - longest << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  for (int tt = 0; tt < t; ++tt) {
    solve();
  }
  return 0;
}
