/**
 * @author n685
 * @date 2025-01-27 12:46:06
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

template <class T> struct CC {
  std::vector<T> val;
  void insert(T a) { val.push_back(a); }
  void init() {
    std::sort(val.begin(), val.end());
    val.erase(std::unique(val.begin(), val.end()), val.end());
  }
  int operator[](T a) const {
    return static_cast<int>(
      std::distance(val.begin(), std::lower_bound(val.begin(), val.end(), a)));
  }
  int size() const { return static_cast<int>(val.size()); }
};

struct Node {
  int i, l, r;
  bool operator==(const Node& rhs) const = default;
  auto operator<=>(const Node& rhs) const = default;
  bool can_merge(const Node& rhs) const {
    return rhs.l - r == 1 || l - rhs.r == 1;
  }
  Node merge(const Node& rhs) const {
    return {i, std::min(l, rhs.l), std::max(r, rhs.r)};
  }
};

void tc() {
  int n;
  std::cin >> n;

  std::vector<int> a(n);
  for (int& v : a) {
    std::cin >> v;
    --v;
  }

  auto good = [&](int l, int r) {
    CC<int> cc;
    for (int i = l; i <= r; ++i) {
      cc.insert(a[i]);
    }
    cc.init();
    std::set<Node> s;
    for (int i = l; i <= r; ++i) {
      int v = cc[a[i]];
      s.emplace(i, v, v);
    }
    std::queue<int> q;
    for (auto it = s.begin(), nxt = std::next(it); nxt != s.end(); ++it, ++nxt)
    {
      if (it->can_merge(*nxt)) {
        q.emplace(it->i);
      }
    }
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      auto it = s.lower_bound(Node{i, 0, 0});
      if (it == s.end() || std::next(it) == s.end() || it->i != i) {
        continue;
      }
      Node n1 = *it;
      Node n2 = *std::next(it);
      if (n1.can_merge(n2)) {
        s.erase(it);
        s.erase(n2);
        auto it2 = s.insert(n1.merge(n2)).first;
        if (it2 != s.begin()) {
          auto pre = std::prev(it2);
          if (pre->can_merge(*it2)) {
            q.push(pre->i);
          }
        }
        if (std::next(it2) != s.end()) {
          auto nxt2 = std::next(it2);
          if (it2->can_merge(*nxt2)) {
            q.push(it2->i);
          }
        }
      }
    }
    return s.size() == 1;
  };

  int ans = n;
  int i = 0;
  while (i < n) {
    --ans;
    int r = i;
    int d = 1;
    while (good(i, r) && r < n - 1) {
      r = std::min(r + d, n - 1);
      d *= 2;
    }
    int l = i;
    while (l < r) {
      int mid = (l + r + 1) / 2;
      if (good(i, r)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    dbg(i, l);
    i = l + 1;
  }

  std::cout << ans << '\n';
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 0; i < t; ++i) {
    dbg(i + 1);
    tc();
    bar();
  }
}