#include<bits/stdc++.h> //exp:30score
#define int long long
using namespace std;
char a[8011];
int n,ans;
int dp[8011][8011];
signed main()
{
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i) 
	{
		cin>>a[i];
		if(a[i]==a[i-1]) dp[i-1][i]=1,ans++;
	}
	for(int l=3;l<=n;++l)
	{
		for(int i=1;i+l-1<=n;++i)
		{
			int j=i+l-1;
			bool flag=0;
			for(int k=i;k<j;++k)
			{
				if(dp[i][k]&&!dp[k+1][j]||!dp[i][k]&&dp[k+1][j]) break; 
				if(dp[i][k]&&dp[k+1][j])
				{
					ans++;
					dp[i][j]=1;
					flag=1;
					break;
				} 
			}
			if(!flag&&a[i]==a[j]&&dp[i+1][j-1]) dp[i][j]=1,ans++; 
		}
	}
	cout<<ans;
	return 0;
}