#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
template <class T>
ostream& operator<<(ostream& os, vector<T> V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <typename T, typename U>
pair<T, U> operator+(const pair<T, U>& l, const std::pair<T, U>& r) {
  return {l.first + r.first, l.second + r.second};
}
const long long int mod = 1e9 + 7;
const int maxn = 3005;
long long int a[maxn];
long long int dp[maxn][maxn];
vector<long long int> f[maxn];
long long int n;
long long int solve(long long int l, long long int r) {
  if (l == r) return 0;
  if (l == r - 1) return (a[l] != a[r]);
  long long int& res = dp[l][r];
  if (res != -1) return res;
  res = r - l;
  res = min(res, 1 + solve(l + 1, r));
  res = min(res, 1 + solve(l, r - 1));
  for (auto v : f[a[l]]) {
    if (v > l and v <= r) {
      res = min(res, solve(l, v - 1) + solve(v, r));
    }
  }
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (long long int i = 0; i <= n; i++) f[i].clear();
    for (long long int i = 0; i < n; i++) {
      cin >> a[i];
      a[i]--;
      f[a[i]].push_back(i);
      for (long long int j = i; j < n; j++) dp[i][j] = -1;
    }
    cout << solve(0, n - 1) << '\n';
  }
}

### Prompt

Please provide a CPP coded solution to the problem described below:

You are given a 1 by n pixel image. The i-th pixel of the image has color a_i. For each color, the number of pixels of that color is at most 20.

You can perform the following operation, which works like the bucket tool in paint programs, on this image: 

  * pick a color — an integer from 1 to n; 
  * choose a pixel in the image; 
  * for all pixels connected to the selected pixel, change their colors to the selected color (two pixels of the same color are considered connected if all the pixels between them have the same color as those two pixels). 



Compute the minimum number of operations needed to make all the pixels in the image have the same color.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^3).

The first line of each test case contains a single integer n (1 ≤ n ≤ 3⋅10^3) — the number of pixels in the image.

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the colors of the pixels in the image.

Note: for each color, the number of pixels of that color is at most 20.

It is guaranteed that the sum of n over all test cases does not exceed 3⋅10^3.

Output

For each test case, print one integer: the minimum number of operations needed to make all the pixels in the image have the same color.

Example

Input


3
5
1 2 3 2 1
4
1 1 2 2
5
1 2 1 4 2


Output


2
1
3

Note

In the first example, the optimal solution is to apply the operation on the third pixel changing its color to 2 and then to apply the operation on any pixel that has color 2 changing its color and the color of all pixels connected to it to 1. The sequence of operations is then: [1, 2, 3, 2, 1] → [1, 2, 2, 2, 1] → [1, 1, 1, 1, 1].

In the second example, we can either change the 1s to 2s in one operation or change the 2s to 1s also in one operation.

In the third example, one possible way to make all the pixels have the same color is to apply the operation on the first, third and the fourth pixel each time changing its color to 2.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
template <class T>
ostream& operator<<(ostream& os, vector<T> V) {
  os << "[ ";
  for (auto v : V) os << v << " ";
  return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <typename T, typename U>
pair<T, U> operator+(const pair<T, U>& l, const std::pair<T, U>& r) {
  return {l.first + r.first, l.second + r.second};
}
const long long int mod = 1e9 + 7;
const int maxn = 3005;
long long int a[maxn];
long long int dp[maxn][maxn];
vector<long long int> f[maxn];
long long int n;
long long int solve(long long int l, long long int r) {
  if (l == r) return 0;
  if (l == r - 1) return (a[l] != a[r]);
  long long int& res = dp[l][r];
  if (res != -1) return res;
  res = r - l;
  res = min(res, 1 + solve(l + 1, r));
  res = min(res, 1 + solve(l, r - 1));
  for (auto v : f[a[l]]) {
    if (v > l and v <= r) {
      res = min(res, solve(l, v - 1) + solve(v, r));
    }
  }
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (long long int i = 0; i <= n; i++) f[i].clear();
    for (long long int i = 0; i < n; i++) {
      cin >> a[i];
      a[i]--;
      f[a[i]].push_back(i);
      for (long long int j = i; j < n; j++) dp[i][j] = -1;
    }
    cout << solve(0, n - 1) << '\n';
  }
}

```