#include <bits/stdc++.h>
using namespace std;
int q, n;
int A[300005];
int len[300005];
int solve(int size) {
  unordered_map<int, int> last, first;
  int ans = 0;
  last[0] = -1;
  for (int i = 0; i < n; i++) last[A[i]] = i;
  for (int i = n - 1; i >= 0; i--) first[A[i]] = i;
  for (int i = 0; i < n; i++) {
    if (i == last[A[i]] && last[A[i] - 1] < first[A[i]]) {
      len[A[i]] = len[A[i] - 1] + 1;
    } else {
      len[A[i]] = 1;
    }
    ans = max(ans, len[A[i]]);
  }
  return size - ans;
}
int main() {
  ;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> q;
  while (q--) {
    cin >> n;
    vector<int> v(n);
    set<int> s;
    unordered_map<int, int> m;
    for (int i = 0; i < n; i++) {
      cin >> A[i];
      s.insert(A[i]);
    }
    int cont = 1;
    for (auto i : s) m[i] = cont++;
    for (int i = 0; i < n; i++) A[i] = m[A[i]];
    cout << solve(s.size()) << '\n';
  }
  return 0;
}
