#include <bits/stdc++.h>
using namespace std;
long long d[1000005], l[1000005], r[1000005], q, n, tag[1000005], a[1000005],
    num[1000005];
long long inf = 1000000000000000000, mod = 1000000007, BS, k;
int main() {
  cin >> q;
  while (q--) {
    cin >> n;
    for (long long i = 1; i <= n; i++) {
      tag[i] = 0;
      l[i] = 0;
      r[i] = 0;
    }
    long long maxsiz = 0;
    map<long long, long long> mp;
    for (long long i = 1; i <= n; i++) {
      scanf("%lld", &a[i]);
      mp[a[i]];
      num[i] = i;
      d[i] = 0;
    }
    for (auto &it : mp) it.second = ++maxsiz;
    for (long long i = 1; i <= n; i++) a[i] = mp[a[i]], tag[a[i]] = 1;
    long long t = 1;
    for (long long i = 1; i <= n; i++) {
      if (tag[i] == 1) {
        tag[i] = t;
        t++;
      }
    }
    for (long long i = 1; i <= n; i++) {
      a[i] = tag[a[i]];
      if (l[a[i]] == 0) l[a[i]] = i;
      r[a[i]] = i;
    }
    d[1] = 1;
    long long ma = 1;
    for (long long i = 2; i < t; i++) {
      if (l[i] > r[i - 1]) {
        d[i] = d[i - 1] + 1;
      } else
        d[i] = 1;
      ma = max(d[i], ma);
    }
    cout << t - 1 - ma << endl;
  }
}
