#include <bits/stdc++.h>
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    int n;
    scanf("%d", &n);
    const int INF = 0x3f3f3f3f;
    std::vector<int> pmin(n + 1, INF), pmax(n + 1, -INF), s(n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &s[i]);
      pmin[s[i]] = std::min(pmin[s[i]], i);
      pmax[s[i]] = std::max(pmax[s[i]], i);
    }
    std::sort(s.begin(), s.end());
    s.erase(std::unique(s.begin(), s.end()), s.end());
    std::vector<bool> conn(s.size() - 1, false);
    for (int i = 0; i + 1 < s.size(); ++i)
      conn[i] = pmax[s[i]] < pmin[s[i + 1]];
    int result = s.size();
    for (int i = 0, j = 0; i < s.size(); i = j = j + 1) {
      while (j + 1 < s.size() && conn[j]) ++j;
      result = std::min(result, (int)s.size() - (j - i + 1));
    }
    printf("%d\n", result);
  }
}
