#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
const int MAXN = 3e5 + 20;
const int oo = 0x3f3f3f3f;
int a[MAXN], dp[MAXN];
vector<int> unq, app[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  int q, n;
  cin >> q;
  while (q--) {
    cin >> n;
    unq.clear();
    for (register int i = (1); i <= (n); ++i) {
      cin >> a[i];
      unq.push_back(a[i]);
    }
    sort((unq).begin(), (unq).end());
    unq.erase(unique((unq).begin(), (unq).end()), unq.end());
    for (register int i = (0); i <= ((int((unq).size())) - 1); ++i) {
      dp[i] = 1;
      app[i].clear();
    }
    for (register int i = (1); i <= (n); ++i) {
      app[a[i] = lower_bound((unq).begin(), (unq).end(), a[i]) - unq.begin()]
          .push_back(i);
    }
    app[(int((unq).size())) - 1].push_back(+oo);
    for (register int i = ((int((unq).size())) - 2); i >= (0); --i) {
      int l = app[i].front(), r = app[i].back();
      int k = lower_bound((app[i + 1]).begin(), (app[i + 1]).end(), l) -
              app[i + 1].begin();
      if (app[i + 1][k] > r && app[i + 1].front() > r) dp[i] += dp[i + 1];
      app[i].push_back(+oo);
    }
    int res = 0;
    for (register int i = (0); i <= ((int((unq).size())) - 1); ++i) {
      res = max(res, dp[i]);
    }
    cout << (int((unq).size())) - res << '\n';
  }
  return 0;
}
