#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
const int oo = 1e9;
const int N = 3e5 + 5;
int a[N];
int cnt[N];
int lef[N], rig[N];
int f(int l, int r, int dir) {
  if (l > r) return 0;
  for (int i = l; i <= r; i++) {
  }
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int n;
    scanf("%d", &n);
    map<int, int> ma;
    for (int i = 0; i < n; i++) {
      scanf("%d", a + i);
      if (i && a[i] == a[i - 1]) {
        i--;
        n--;
        continue;
      }
      ma[a[i]] = 0;
    }
    int id = 0;
    for (auto &i : ma) {
      i.second = ++id;
      cnt[id] = 0;
      lef[id] = -1;
      rig[id] = -1;
    }
    for (int i = 0; i < n; i++) {
      a[i] = ma[a[i]];
      cnt[a[i]]++;
      rig[a[i]] = i;
      if (lef[a[i]] == -1) lef[a[i]] = i;
    }
    int ans = 1;
    int i = 1;
    while (i < id) {
      int x = 1;
      int at = i;
      i++;
      while (i <= id && lef[i] > rig[i - 1]) {
        x++;
        i++;
      }
      ans = max(ans, x);
    }
    printf("%d\n", id - ans);
  }
  return 0;
}
