#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <typename T>
inline void umax(T &a, T b) {
  a = max(a, b);
}
template <typename T>
inline void umin(T &a, T b) {
  a = min(a, b);
}
const long long N = 1e5 + 10;
const long long INF = 1e16 + 10;
const pair<long long, long long> NINF = make_pair(INF, INF);
const long double EPS = 1e-6;
const long long II = 1e9;
const long long MOD = 1e9 + 7;
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    long long n;
    cin >> n;
    vector<pair<long long, long long> > ar(n);
    for (long long i = 0; i < (n); i++) cin >> ar[i].first, ar[i].second = i;
    sort(ar.begin(), ar.end());
    vector<long long> r(n);
    r[n - 1] = n - 1;
    for (long long i = n - 2; i >= 0; i--)
      if (ar[i].second < ar[i + 1].second)
        r[i] = r[i + 1];
      else
        r[i] = i;
    vector<long long> ff(n), bb(n);
    set<long long> second;
    for (long long i = 0; i < (n); i++) {
      second.insert(ar[i].first);
      ff[i] = second.size();
    }
    second.clear();
    for (long long i = n - 1; i >= 0; i--) {
      second.insert(ar[i].first);
      bb[i] = second.size();
    }
    long long ans = INF;
    for (long long i = 0; i < (n); i++) {
      long long _ff = i ? ff[i - 1] : 0LL,
                _bb = r[i] != n - 1 ? bb[r[i] + 1] : 0LL;
      umin(ans, _ff + _bb);
    }
    cout << ans << '\n';
  }
}
