#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=8010;
int sum;
bool num[N][N];
bool f[N][N];
vector<int> g[N];
signed main(){
	int n;cin>>n;
	string s;cin>>s;
	s=' '+s;
	for(int i=1;i<n;i++){
		map<char,int> now;
		if(s[i]==s[i+1]) num[i][i+1]=1;
		now[s[i]]++,now[s[i+1]]++;
		for(int j=i+3;j<=n;j+=2){
		    now[s[j-1]]++,now[s[j]]++;
			if(num[i][j-2]){
				if(s[j-1]==s[j]) num[i][j]=1;
				continue;
			}
			bool flag=1;
			for(int k='a';k<='z';k++){
				if(now[k]&1){
					flag=0;
					break;
				}
			}
			if(flag) num[i][j]=1;
		}
	}
	for(int i=2;i<=n;i+=2){
		for(int j=1;j+i-1<=n;j++){
			int l=j,r=j+i-1;
			if(!num[l][r]) continue;
			if(s[l]==s[r]){
				++sum;
				g[l].push_back(r);
				f[l][r]=1;
				continue;
			}
			for(int k=0;k<g[l].size();k++){
				if(f[g[l][k]+1][r]){
					++sum;
					g[l].push_back(r);
					f[l][r]=1;
					break;
				}
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}