#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
const long long int inf = 1e12;
const long long int mod = 1000000007;
long long int gc(long long int a, long long int b) {
  if (b == 0) return a;
  return gc(b, a % b);
}
long long int power(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
vector<bool> prime(1000005, true);
vector<long long int> v;
void sieve(long long int n) {
  prime[1] = false;
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
  for (int i = 2; i <= n; i++) {
    if (prime[i] == true) v.push_back(i);
  }
}
inline long long int add(long long int a, long long int b) {
  return ((a % mod) + (b % mod)) % mod;
}
inline long long int sub(long long int a, long long int b) {
  return ((a % mod) - (b % mod) + mod) % mod;
}
inline long long int mul(long long int a, long long int b) {
  return ((a % mod) * (b % mod)) % mod;
}
long long int recur(long long int idx, long long int sum,
                    vector<pair<long long int, long long int> >& v,
                    vector<long long int>& b, vector<long long int>& pre,
                    vector<long long int>& dp) {
  if (idx == b.size()) return 0;
  if (dp[idx] != -1) return dp[idx];
  long long int temp = INT_MAX;
  temp = min(temp, recur(idx + 1, sum, v, b, pre, dp) + b[idx]);
  for (int i = 0; i < v.size(); i++) {
    long long int x = v[i].first;
    long long int y = v[i].second;
    if (idx + x - 1 >= b.size()) continue;
    long long int calc = pre[idx + x - 1] - pre[idx + y - 1];
    temp = min(temp, recur(idx + x, sum, v, b, pre, dp) + calc);
  }
  dp[idx] = temp;
  return temp;
}
long long int dfs(long long int src, long long int p, vector<long long int>& a,
                  vector<pair<long long int, long long int> > adj[],
                  vector<long long int>& dp) {
  long long int can1 = 0;
  long long int can2 = 0;
  vector<pair<long long int, long long int> >::iterator it;
  for (it = adj[src].begin(); it != adj[src].end(); it++) {
    if (((*it).first == p)) continue;
    long long int st =
        max(0LL, dfs((*it).first, src, a, adj, dp) - (*it).second);
    if (st > can1) {
      can2 = can1;
      can1 = st;
    } else if (st > can2) {
      can2 = st;
    }
  }
  dp[src] = a[src] + can1 + can2;
  return (max(can1, can2) + a[src]);
}
struct comp1 {
  bool operator()(pair<long long int, long long int>& temp1,
                  pair<long long int, long long int>& temp2) {}
};
bool comp2(pair<long long int, long long int>& temp1,
           pair<long long int, long long int>& temp2) {
  return ((temp1.first < temp2.first) ||
          ((temp1.first == temp2.first) && (temp1.second < temp2.second)));
}
long long int getinv(long long int temp) { return power(temp, mod - 2, mod); }
void computeLPSArray(string pat, long long int M, vector<long long int>& lps) {
  int len = 0;
  lps[0] = 0;
  long long int i = 1;
  while (i < M) {
    if (pat[i] == pat[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
}
long long int fin(long long int u, vector<long long int>& parent) {
  if (u == parent[u])
    return u;
  else
    return parent[u] = fin(parent[u], parent);
}
void unio(long long int u, long long int v, vector<long long int>& parent,
          vector<long long int>& ran) {
  u = fin(u, parent);
  v = fin(v, parent);
  if (u == v) return;
  if (ran[u] >= ran[v]) {
    parent[v] = u;
    ran[u] += ran[v];
  } else {
    parent[u] = v;
    ran[v] += ran[u];
  }
}
void update(int x, int delta, vector<long long int>& BIT) {
  long long int n = BIT.size() - 1;
  for (; x <= n; x += x & -x) BIT[x] += delta;
}
int query(int x, vector<long long int>& BIT) {
  int sum = 0;
  for (; x > 0; x -= x & -x) sum += BIT[x];
  return sum;
}
int main() {
  long long int t;
  cin >> t;
  while (t--) {
    long long int n;
    cin >> n;
    long long int a[n];
    vector<long long int> v;
    for (long long int i = 0; i < n; i++) {
      cin >> a[i];
      v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    vector<long long int> b(n);
    map<long long int, long long int> m;
    vector<bool> vis(n, false);
    for (long long int i = 0; i < n; i++) {
      long long int idx = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
      b[i] = idx;
    }
    set<long long int> s;
    for (long long int i = 0; i < n; i++) {
      s.insert(b[i]);
    }
    vector<long long int> dp(n, 0);
    long long int ans = 0;
    set<long long int>::iterator it;
    map<long long int, long long int> m1;
    long long int last = -1;
    long long int lcount = 0;
    for (long long int i = 0; i < n; i++) {
      if (last == b[i]) {
        lcount++;
      } else {
        lcount = 1;
        last = b[i];
      }
      it = s.lower_bound(b[i]);
      if (it == s.begin()) {
        long long int p = (*it);
        m1[p]++;
        dp[p] = m1[p];
        ans = max(ans, m1[p]);
      } else {
        it--;
        long long int prev = (*it);
        if (m1.find(b[i]) == m1.end()) {
          dp[b[i]] = dp[prev] + 1;
          m1[b[i]]++;
        } else {
          dp[b[i]] = dp[prev] + lcount;
          m1[b[i]]++;
        }
        ans = max(ans, dp[b[i]]);
      }
    }
    cout << n - ans << endl;
  }
}
