#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
int n, l[300005], r[300005], mx, an;
bool vi[300005];
vector<int> v;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      l[i] = 1e9;
      r[i] = -1e9;
      vi[i] = false;
    }
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      l[x] = min(l[x], i);
      r[x] = max(r[x], i);
      if (vi[x] == false) v.push_back(x);
      vi[x] = true;
    }
    sort(v.begin(), v.end());
    an = 1;
    mx = 0;
    for (int i = 1; i < v.size(); i++) {
      mx = max(mx, an);
      if (l[v[i]] > r[v[i - 1]])
        an++;
      else
        an = 1;
    }
    mx = max(mx, an);
    cout << v.size() - mx << endl;
    v.clear();
  }
}
