一道很有意思的题，但是思考以后就会发现，绝对不会出现一对相邻的字符不相同，因为不相同且相邻的都消掉了，所以就找最多出现次数的那一个字符。

如果最多出现的字符超过了字符总数的一半，那么这个字符串的长度只能是该字符的数量减去其余字符的总数，因为如果要保证最短的话，其余字符都要带走一个该字符。消减完以后的字符串里面一定只剩最多出现的那个字符了

如果出现的字符数小于等于字符总数的一半，那么就直接把字符总数对2取余即可。其余字符每一个都和一个最大出现次数的字符相消。

#include<bits/stdc++.h>
using namespace std;
int cnt[27];
int main(){
    int t; cin>>t;
    while(t--){
        memset(cnt,0,sizeof(cnt));
        int n; cin>>n;
        string s; cin>>s;
        for(int i=0;i<s.size();i++){
            cnt[s[i]-'a']++;
        }
        int maxn=0;
        for(int i=0;i<26;i++){
            maxn=max(maxn,cnt[i]);
        }
        if(maxn*2<=n){
            cout<<n%2<<'\n';
        }
        else{
            cout<<maxn-(n-maxn)<<'\n';
        }
    }
    return 0;
}