#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool uax(T &x, T y) {
  return (y > x) ? x = y, true : false;
}
template <typename T>
inline bool uin(T &x, T y) {
  return (y < x) ? x = y, true : false;
}
template <typename T>
void kek(T ans) {
  cout << ans << endl;
  exit(0);
}
const int MOD = (int)1e9 + 7;
const long long INF = (long long)1e18 + 42;
void solve_case() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x;
  auto b = a;
  sort(begin(b), end(b));
  b.erase(unique(begin(b), end(b)), end(b));
  int m = int((b).size());
  vector<int> val(m + 1);
  int ans = n;
  for (int &x : a) {
    x = lower_bound(begin(b), end(b), x) - begin(b);
    int l = val[x];
    if (x) uax(l, val[x - 1]);
    ++l;
    uin(ans, n - l);
    val[x] = l;
  }
  42;
  ;
  42;
  ;
  cout << ans << '\n';
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tt;
  cin >> tt;
  while (tt--) {
    solve_case();
  }
}
