static int solve(int a, int b) {
		if (a >= n)
			return 0;
		if (dp[a][b] != 0)
			return dp[a][b];
		if (a == b)
			return dp[a][b] = 1;
		int r = b - a + 1;
		for (int i = a; i <= b; i++)
			for (int l = 1; l <= i - a + 1; l++) 
				if (check(a, i, l)) {
					if (i == b && l == (b - a + 1))
						continue;
					r = Math.min(r, solve(a, a + l - 1) + solve(i + 1, b));
				}
		return dp[a][b] = r;
	}