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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Comparator;

public class Main extends PrintWriter {

    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    // static Scanner s=new Scanner(System.in);
    Main () { super(System.out); }
    public static void main(String[] args) throws IOException{
        Main  d1=new Main   ();d1.main();d1.flush();
    }
    void main() throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        StringBuffer sb1 = new StringBuffer();
        PrintWriter out = new PrintWriter(System.out);
        int t=1;
//        t=i(s()[0]);
        while(t-->0) {
            //dp[i]=a[i]+max(dp[j]) S.T. j<i and h[j]<h[i];
            String[] s1=s();
            int n=i(s1[0]);
            char[] a=s()[0].toCharArray();
            StringBuffer sbb=new StringBuffer();
            sbb.append(a[0]);
            for(int i=1;i<n;i++){
                if(a[i]!=a[i-1]){
                    sbb.append(a[i]);
                }
            }long[][] dp=new long[n][n];
            char[] b=a;

            for(int width=0;width<=n-1;width++){
                for(int i=0;i<n-width;i++){
                    if(width==0){
                        dp[i][i]=1;
                    }else if(width==1){
                        if(b[i]==b[i+1]) dp[i][i+1]=1;
                        else dp[i][i+1]=2;
                    }else  if(width>1){
                       dp[i][i+width]=1+dp[i+1][i+width];
                   }
                    for(int j=i+1;j<=i+width;j++){
                 {
                        if (b[i] == b[j]) {
                            dp[i][i + width] = Math.min(dp[i][i+width],dp[i+1][j-1]+dp[j][i+width]);
                       }
                    }
                   }
//                    System.out.println(i+" "+(i+width)+" "+dp[i][i+width]);
                }
            }
            System.out.println(dp[0][n-1]);
        }
    }
    //        System.out.println(sb);
    long[] st;
    void buildtree(int i,int s,int e,long[] a){
        if(s==e){
            st[i]=a[s];
            return;
        }
        int mid=(s+e)/2;
        buildtree(2*i,s,mid,a);
        buildtree(2*i+1,mid+1,e,a);
        st[i]=Math.min(st[2*i],st[2*(i)+1]);
    }
    long query(int i,int s,int e,int qs,int qe){
        if(qs>e||qe<s) return Integer.MIN_VALUE;
        if(s>=qs&&e<=qe) return st[i];
        int mid=(s+e)/2;
        long l=query(2*i,s,mid,qs,qe);
        long r=query(2*i+1,mid+1,e,qs,qe);
        return Math.max(l,r);
    }
    void pointupdate(int i,int s,int e,int qi,long [] a){
        if(s==e){
            st[i]=a[s];return;
        }
        int mid=(s+e)/2;
        if(qi<=mid) pointupdate(2*i,s,mid,qi,a);
        else pointupdate(2*(i)+1,mid+1,e,qi,a);
        st[i]=Math.max(st[2*i],st[2*i+1]);
    }
    public void arr(long[] a,int n) throws IOException{
        //        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        String[] s2=s();
        for(int i=0;i<n;i++){
            a[i]=i(s2[i]);
        }
    }
    public void sort(int[] a,int l,int h){
        if(l==h) return;
        int mid=(l+h)/2;

        sort(a,l,mid);
        sort(a,mid+1,h);
        merge(a,l,(l+h)/2,h);
    }
    void merge(int arr[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }


    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static String[] s() throws IOException {
        return s.readLine().trim().split("\\s+");
    }

    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }
}
class Student {
    long  a;int b;int c;
    public Student(int a,int b) {
        this.a=a;this.c=c;this.b=b;
    }
}
class Pair {
    int  a,b,c;
    public Pair(int  a,int b){
        this.a=a;this.b=b;this.c=c;}
}
class Sortbyroll implements Comparator<Student> {

    public int compare(Student a, Student b){
        if(a.b==b.b) return (int)b.a-(int)a.a;
        return   a.b-b.b;}
}