#include <bits/stdc++.h>
using namespace std;
long long seq[303030];
long long dp[303030];
long long last[303030];
long long firstind[303030], lastind[303030];
vector<long long> v;
bool seen[303030];
void solve() {
  v.clear();
  long long n;
  cin >> n;
  long long maxfixed = 0;
  for (long long i = 1; i <= n; i++) {
    firstind[i] = 0x3f3f3f3f;
    lastind[i] = 0;
    last[i] = 0;
    dp[i] = 1;
    seen[i] = false;
  }
  for (long long i = 1; i <= n; i++) {
    cin >> seq[i];
    v.push_back(seq[i]);
    seen[seq[i]] = true;
    firstind[seq[i]] = min(firstind[seq[i]], i);
    lastind[seq[i]] = max(lastind[seq[i]], i);
  }
  sort(((v).begin()), ((v).end()));
  v.erase(unique(((v).begin()), ((v).end())), v.end());
  long long ss = v.size();
  for (long long i = 1; i < ss; i++) last[v[i]] = v[i - 1];
  dp[0] = 0;
  for (long long i = 1; i <= n; i++) {
    if (!seen[i]) continue;
    if (firstind[i] > lastind[last[i]]) {
      dp[i] = max(dp[i], dp[last[i]] + 1);
    } else
      continue;
  }
  for (long long i = 1; i <= n; i++) {
    maxfixed = max(maxfixed, dp[i]);
  }
  cout << ss - maxfixed << '\n';
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    solve();
  }
}
