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.*;
import java.util.HashMap;
import java.util.InputMismatchException;

/**
 * @author solarbeam
 */

public class CF1132F {
    public static void main(String[] args) throws FileNotFoundException, InterruptedException {
        InputStream stream = System.in;
        Logger logger = new Logger();
        if (args.length > 0 && args[0].equals("LOCAL")) {
            File inputFile = new File("resources/input.in");
            stream = new DataInputStream(new FileInputStream(inputFile));
            logger.enableLogging(true, "resources/logs.txt");
        }
        InputReader in = new InputReader(stream);
        PrintWriter out = new PrintWriter(System.out);
        Runnable solver = () -> {
            new Task1().solve(in, out, logger);
        };
        Thread th = new Thread(null, solver, "Task1", 1 << 24);
        th.start();
        th.join();
        out.close();
        logger.close();
    }

    static class Task1 {
        String s;
        Integer[][] dp;
        public void solve(InputReader in, PrintWriter out, Logger logger) {
            int n = in.nextInt();
            s = in.next();
            dp = new Integer[s.length()][s.length()];
            out.println(deleteTheString(0, n-1));
        }

        int deleteTheString(int l, int r){
            if(l==r) return 1;
            if(l>r) return 0;
            if(dp[l][r] != null) return dp[l][r];
            int answer = 1+deleteTheString(l+1, r);

            for(int i=l+1; i<=r; i++){
                if(s.charAt(i)==s.charAt(l)){
                    answer = Math.min(answer, deleteTheString(l+1, i-1)+deleteTheString(i, r));
                }
            }
            return dp[l][r] = answer;
        }
    }

    static class Logger {
        private PrintWriter logger;
        private boolean enableLogging;

        public void enableLogging(boolean enableLogging, String filename) {
            this.enableLogging = enableLogging;
            try {
                if (enableLogging) this.logger = new PrintWriter(filename);
            } catch (FileNotFoundException e) {
            }
        }

        public void log(Object s) {
            if (enableLogging) {
                logger.print(s.toString());
            }
        }

        public void logln(Object s) {
            if (enableLogging) {
                logger.println(s.toString());
            }
        }

        public void close() {
            if (enableLogging) logger.close();
        }
    }

    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, numChars;
        private SpaceCharFilter filter;

        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 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 String next() {
            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 interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}