Problem: You are given a string s of length n consisting of lowercase Latin letters. You may apply some operations to this string: in one operation you can delete some contiguous substring of this string, if all letters in the substring you delete are equal. For example, after deleting substring bbbb from string abbbbaccdd we get the string aaccdd.

Calculate the minimum number of operations to delete the whole string s.

Input

The first line contains one integer n (1 ≤ n ≤ 500) — the length of string s.

The second line contains the string s (|s| = n) consisting of lowercase Latin letters.

Output

Output a single integer — the minimal number of operation to delete string s.

Examples

Input


5
abaca


Output


3

Input


8
abcddcba


Output


4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y, long long int m) {
  if (y == 0) return 1;
  long long int a = power(x, y / 2, m);
  if (y % 2) {
    return (a * ((a * x) % m)) % m;
  } else {
    return (a * a) % m;
  }
}
long long int mod_inverse(long long int x, long long int m) {
  return power(x, m - 2, m);
}
long long int fact(long long int n, long long int m) {
  if (n <= 1) return 1;
  return (fact(n - 1, m) * n) % m;
}
long long int ncr(long long int n, long long int r, long long int m) {
  if (r > n) return 0;
  long long int n1 = 1, d1 = 1, d2 = 1;
  n1 = fact(n, m);
  d1 = fact(r, m);
  d2 = fact(n - r, m);
  long long int ans = mod_inverse((d1 * d2) % m, m);
  ans = (ans * n1) % m;
  return ans;
}
int ispal(string s) {
  int len = s.size();
  int flag = 1;
  for (int i = 0; i < len; ++i) {
    if (s[i] != s[len - i - 1]) {
      flag = 0;
      break;
    }
  }
  return flag;
}
long long int sroot(long long int n, long long int low = 1,
                    long long int high = 1e9 + 1) {
  if (low == high) return low;
  if (low == high - 1) {
    if (high * high <= n)
      return high;
    else
      return low;
  }
  long long int mid = (low + high) / 2;
  long long int a = mid * mid;
  if (a > n)
    return sroot(n, low, mid - 1);
  else
    return sroot(n, mid, high);
}
long long int croot(long long int n, long long int low = 1,
                    long long int high = 1e6 + 1) {
  if (low == high) return low;
  if (low == high - 1) {
    if (high * high * high <= n)
      return high;
    else
      return low;
  }
  long long int mid = (low + high) / 2;
  long long int a = mid * mid * mid;
  if (a > n)
    return croot(n, low, mid - 1);
  else
    return croot(n, mid, high);
}
pair<int, int> operator+(pair<int, int> p1, pair<int, int> p2) {
  return {p1.first + p2.first, p1.second + p2.second};
}
class solver {
 public:
  void solve() {
    int len;
    cin >> len;
    string s;
    cin >> s;
    s = '#' + s;
    vector<int> a;
    a.push_back(-1);
    for (int i = 1; i <= len;) {
      int x = int(s[i]) - int('a') + 1;
      char ch = s[i];
      a.push_back(x);
      while (i <= len && s[i] == ch) i++;
    }
    int n = a.size() - 1;
    int dp[n + 1][n + 1];
    memset(dp, -1, sizeof(dp));
    for (int ln = 1; ln <= n; ++ln) {
      for (int i = 1; i <= n; ++i) {
        int j = i + ln - 1;
        if (j > n) continue;
        if (i == j) {
          dp[i][j] = 1;
          continue;
        }
        int mn = dp[i + 1][j] + 1;
        if (a[i + 1] == a[i]) mn = min(mn, dp[i + 1][j]);
        for (int k = i + 2; k <= j; ++k) {
          if (a[i] == a[k]) mn = min(mn, dp[i + 1][k - 1] + dp[k][j]);
        }
        dp[i][j] = mn;
      }
    }
    cout << dp[1][n] << '\n';
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int test = 1;
  while (test--) {
    solver o;
    o.solve();
  }
}