#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 5;
const int inf = 1e9;
int dp[maxn][maxn], a[maxn], pos[maxn], nxt[maxn], pre[maxn], b[maxn];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    int nn = n;
    int tot = 0;
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &b[i]);
      if (i == 1 || b[i] != b[i - 1]) a[++tot] = b[i];
    }
    n = tot;
    for (int i = 1; i <= n; ++i) {
      pre[i] = pos[a[i]];
      pos[a[i]] = i;
    }
    memset(pos, 0, sizeof(int) * (nn + 2));
    for (int i = n; i >= 1; --i) {
      nxt[i] = pos[a[i]];
      pos[a[i]] = i;
    }
    memset(pos, 0, sizeof(int) * (nn + 2));
    for (int i = 1; i <= n; ++i)
      for (int j = i + 1; j <= n; ++j) dp[i][j] = inf;
    for (int len = 2; len <= n; ++len) {
      for (int i = 1; i <= n - len + 1; ++i) {
        int j = i + len - 1;
        int k = i;
        do {
          if (a[i] == a[j])
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
          else
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);
          k = nxt[k];
        } while (k && k < j);
        if (a[i] != a[j]) {
          k = j;
          do {
            dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k][j] + 1);
            k = pre[k];
          } while (k > i);
        }
        dp[i][j] = min(dp[i][j], min(dp[i + 1][j] + 1, dp[i][j - 1] + 1));
      }
    }
    printf("%d\n", dp[1][n]);
  }
}
