#include <bits/stdc++.h>
using namespace std;
struct data {
  int l, r, dp;
};
data tree[1300001];
int arr[300001];
data num[300001];
int ans[300001];
void init(int a, int b, int v) {
  tree[v].dp = 0;
  tree[v].l = a;
  tree[v].r = b;
  if (a == b) {
    return;
  }
  int mid = (tree[v].l + tree[v].r) / 2;
  if (a <= mid) {
    init(a, mid, 2 * v);
  }
  if (b > mid) {
    init(mid + 1, b, 2 * v + 1);
  }
}
int query(int a, int b, int v) {
  if (tree[v].l == a && tree[v].r == b) {
    return tree[v].dp;
  }
  int ans = 0;
  int mid = (tree[v].l + tree[v].r) / 2;
  if (a <= mid) {
    ans = max(ans, query(a, mid, 2 * v));
  }
  if (b > mid) {
    ans = max(ans, query(mid + 1, b, 2 * v + 1));
  }
  return ans;
}
void revise(int c, int v, int k) {
  if (tree[v].l == c && tree[v].r == c) {
    tree[v].dp = k;
    return;
  }
  int mid = (tree[v].l + tree[v].r) / 2;
  if (c <= mid) {
    revise(c, 2 * v, k);
    tree[v].dp = max(tree[v].dp, tree[v * 2].dp);
  }
  if (c > mid) {
    revise(c, 2 * v + 1, k);
    tree[v].dp = max(tree[v].dp, tree[v * 2 + 1].dp);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      num[i].l = 0;
      num[i].r = n + 1;
      ans[i] = 0;
    }
    init(1, n, 1);
    for (int i = 1; i <= n; i++) {
      cin >> arr[i];
      if (num[arr[i]].l == 0) {
        num[arr[i]].l = i;
        num[arr[i]].r = i;
      } else {
        num[arr[i]].r = i;
      }
    }
    int tmp = 0;
    for (int i = 1; i <= n; i++) {
      if (num[i].l == 0) {
        continue;
      }
      if (num[i].l == 1) {
        ans[i] = 1;
      } else {
        if (num[i].l > num[tmp].r) {
          ans[i] = ans[tmp] + 1;
        } else {
          ans[i] = 1;
        }
      }
      tmp = i;
    }
    int res = 0;
    int res1 = 0;
    for (int i = 1; i <= n; i++) {
      res = max(res, ans[i]);
      if (ans[i] > 0) {
        res1++;
      }
    }
    cout << res1 - res << "\n";
  }
}
