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.BufferedOutputStream;
import java.io.InputStream;

public class Task {

    private static int[][] tab = null;

    public static void solve() throws Exception {
	nextInt();
	String str = next();
	char[] arr = str.toCharArray();
	StringBuilder sb = new StringBuilder();
	char prev = '?';
	for (int i = 0; i < arr.length; i++) {
	    char ch = arr[i];
	    if (ch != prev) {
		sb.append(ch);
	    }
	    prev = ch;
	}

	arr = sb.toString().toCharArray();
	int n = arr.length;

	tab = new int[n + 1][n + 1];

	System.out.println(calculate(arr, 0, n - 1));
    }

    private static int calculate(char[] arr, int from, int to) {
	if (from > to) {
	    return 0;
	}

	int len = to - from + 1;

	int ret = tab[from][to];
	if (ret > 0) {
	    return ret;
	}

	if (len == 1) {
	    tab[from][to] = 1;
	    return 1;
	}

	int min = 1 + calculate(arr, from+1, to);;
	char ch = arr[from];
	for (int i = from + 1; i <= to; i++) {
	    if (ch == arr[i]) {
		int ret1 = calculate(arr, from+1, i-1);;
		int ret2 = calculate(arr, i, to);
		min = Math.min(min, ret1 + ret2);
	    }
	}
	tab[from][to] = min;
	return min;
    }

    public static void main(String[] args) throws Exception {
	try {
	    fastReader = new FastReader(System.in);
	    systemOut = new BufferedOutputStream(System.out);
	    solve();
	} finally {
	    systemOut.close();
	}
    }

    private static FastReader fastReader = null;
    private static BufferedOutputStream systemOut = null;

    public static void print(Object obj) {
	print(obj.toString());
    }

    public static void print(String str) {
	try {
	    systemOut.write(str.getBytes("utf-8"));
	} catch (Exception ex) {
	    throw new RuntimeException(ex);
	}
    }

    public static void println(Object obj) {
	println(obj.toString());
    }

    public static void println(String str) {
	try {
	    print(str);
	    systemOut.write('\n');
	} catch (Exception ex) {
	    throw new RuntimeException(ex);
	}
    }

    public static String next() {
	return fastReader.readNextToken(false);
    }

    public static String nextLine() {
	return fastReader.readNextToken(true);
    }

    public static int nextInt() {
	return Integer.parseInt(fastReader.readNextToken(false));
    }

    public static long nextLong() {
	return Long.parseLong(fastReader.readNextToken(false));
    }

    public static double nextDouble() {
	return Double.parseDouble(fastReader.readNextToken(false));
    }

    static class FastReader {
	private byte[] buf = new byte[65536];
	private int ind = 0;
	private int maxInd = -1;
	private InputStream is = null;
	private boolean eof = false;
	private boolean lastCharRead = false;

	public FastReader(InputStream is) {
	    this.is = is;
	}

	public String readNextToken(boolean endOfLine) {
	    try {
		StringBuilder sb = new StringBuilder();
		boolean found = false;
		while (true) {
		    if (lastCharRead) {
			return null;
		    } else if (ind > maxInd) {
			if (eof) {
			    lastCharRead = true;
			} else {
			    fillBuffer();
			}
		    }
		    byte b = '\n';
		    if (!lastCharRead) {
			b = buf[ind++];
		    }

		    if (b == '\r') {
			// ignore
		    } else if ((b == '\n' && endOfLine) || (Character.isWhitespace(b) && !endOfLine)) {
			if (found) {
			    break;
			}
		    } else {
			sb.append((char) b);
			found = true;
		    }
		}
		return sb.toString();
	    } catch (Exception ex) {
		throw new RuntimeException(ex);
	    }
	}

	private void fillBuffer() {
	    try {
		int read = is.read(buf, 0, buf.length);
		if (read < buf.length) {
		    eof = true;
		}
		ind = 0;
		maxInd = read - 1;
	    } catch (Exception ex) {
		throw new RuntimeException(ex);
	    }
	}
    }
}