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.IOException;
 import java.io.InputStream;
 import java.io.PrintWriter;
 import java.io.*;
 import java.util.*;
 import java.util.LinkedList;
 import java.math.*;
 import java.lang.*;
 import java.util.PriorityQueue;
 import static java.lang.Math.*;
 @SuppressWarnings("unchecked")
 public class Solution implements Runnable {
     static class InputReader {
         private InputStream stream;
         private byte[] buf = new byte[1024];
         private int curChar;
         private int numChars;
         private SpaceCharFilter filter;
         private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

         public InputReader(InputStream stream) {
             this.stream = stream;
         }

         public int read() {
             if (numChars==-1)
                 throw new InputMismatchException();

             if (curChar >= numChars) {
                 curChar = 0;
                 try {
                     numChars = stream.read(buf);
                 }
                 catch (IOException e) {
                     throw new InputMismatchException();
                 }

                 if(numChars <= 0)
                     return -1;
             }
             return buf[curChar++];
         }

         public String nextLine() {
             String str = "";
             try {
                 str = br.readLine();
             }
             catch (IOException e) {
                 e.printStackTrace();
             }
             return str;
         }
         public int nextInt() {
             int c = read();

             while(isSpaceChar(c))
                 c = read();

             int sgn = 1;

             if (c == '-') {
                 sgn = -1;
                 c = read();
             }

             int res = 0;
             do {
                 if(c<'0'||c>'9')
                     throw new InputMismatchException();
                 res *= 10;
                 res += c - '0';
                 c = read();
             }
             while (!isSpaceChar(c));

             return res * sgn;
         }

         public long nextLong() {
             int c = read();
             while (isSpaceChar(c))
                 c = read();
             int sgn = 1;
             if (c == '-') {
                 sgn = -1;
                 c = read();
             }
             long res = 0;

             do {
                 if (c < '0' || c > '9')
                     throw new InputMismatchException();
                 res *= 10;
                 res += c - '0';
                 c = read();
             }
             while (!isSpaceChar(c));
                 return res * sgn;
         }

         public double nextDouble() {
             int c = read();
             while (isSpaceChar(c))
                 c = read();
             int sgn = 1;
             if (c == '-') {
                 sgn = -1;
                 c = read();
             }
             double res = 0;
             while (!isSpaceChar(c) && c != '.') {
                 if (c == 'e' || c == 'E')
                     return res * Math.pow(10, nextInt());
                 if (c < '0' || c > '9')
                     throw new InputMismatchException();
                 res *= 10;
                 res += c - '0';
                 c = read();
             }
             if (c == '.') {
                 c = read();
                 double m = 1;
                 while (!isSpaceChar(c)) {
                     if (c == 'e' || c == 'E')
                         return res * Math.pow(10, nextInt());
                     if (c < '0' || c > '9')
                         throw new InputMismatchException();
                     m /= 10;
                     res += (c - '0') * m;
                     c = read();
                 }
             }
             return res * sgn;
         }

         public String readString() {
             int c = read();
             while (isSpaceChar(c))
                 c = read();
             StringBuilder res = new StringBuilder();
             do {
                 res.appendCodePoint(c);
                 c = read();
             }
             while (!isSpaceChar(c));

             return res.toString();
         }

         public boolean isSpaceChar(int c) {
             if (filter != null)
                 return filter.isSpaceChar(c);
             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
         }

         public String next() {
             return readString();
         }

         public interface SpaceCharFilter {
             public boolean isSpaceChar(int ch);
         }
     }
     public static long min(long a,long b)
     {
         if(a>b)
         {
             return b;
         }
         return a;
     }
     public static int min(int a,int b)
     {
         if(a>b)
         {
             return b;
         }
         return a;
     }
     public static long max(long a,long b)
     {
         if(a>b)
         {
             return a;
         }
         return b;
     }
     public static int max(int a,int b)
     {
         if(a>b)
         {
             return a;
         }
         return b;
     }
     static class pair implements Comparable<pair>
     {
       int x;
       int y;
       pair(int x,int y)
       {
         this.x = x;
         this.y = y;
       }
       public int compareTo(pair b)
       {
         if(this.x>b.x)
         {
           return 1;
         }
         else if(this.x<b.x)
         {
           return -1;
         }
         else
         {
           return this.y-b.y;
         }
       }
     }
     public static int gcd(int a,int b)
     {
         if(a==0)
         return b;
         if(b==0)
         return a;
         while((a%=b)!=0&&(b%=a)!=0);
         return a^b;
     }
     public static long mod(long a)
     {
       if(a>0)
         return a;
       return -a;
     }
     static final int mod = (int)1e9+7;;
     public static long expo(long exp,long pow)
     {
       long ans = 1;
       while(pow!=0)
       {
         if((pow&1)==1)
         {
           ans = (ans*exp)%mod;
         }
         exp = (exp*exp)%mod;
         pow = pow>>1;
       }
       return ans;
     }
     static long start = 0;
     public static void start()
     {
       start = System.currentTimeMillis();
     }
     public static void end()
     {
       System.out.println(System.currentTimeMillis()-start);
     }
     public static int random(int min,int max)
     {
       return min+(int)((max-min)*Math.random());
     }
     public static String randString(int len)
     {
       String s = "";
       while(len-->0)
       {
           char c = (char)(97+random(0,26));
           s+=c;
       }
       return s;
     }
     public static void main(String args[]) throws Exception {
         new Thread(null, new Solution(),"Main",1<<26).start();
     }
     public void run() {
       InputReader sc  = new InputReader(System.in);
       PrintWriter out = new PrintWriter(System.out);
       int t1 = 1;
         //start();
       while(t1-->0)
       {
         int n = sc.nextInt();
         char[] c = sc.readString().toCharArray();
         int[][] dp = new int[n][n];
         for(int i=0;i<n;i++)
         {
           dp[i][i] = 1;
         }
         for(int l1=2;l1<=n;l1++)
         {
           for(int l2=0;l2<n-l1+1;l2++)
           {
             int i = l2;
             int j = l2+l1-1;
             dp[i][j] = dp[i][j-1]+1;
             for(int k=i;k<j;k++)
             {
               if(c[k]==c[j])
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j-1]);
             }
           }
         }
         out.println(dp[0][n-1]);
       }
       //end();
       out.close();
      }
 }