#include <bits/stdc++.h> #define LL long long using namespace std; const int MAXN=1e5+5; LL ans=0; int N,T; char s[MAXN],loop[10]; int Find(int len) { int i=1,j=1,res=0; for(int i=1;i<=N;i++) { if(s[i]==loop[j]) { j++; if(j==len+1) { res++; j=1; } } } return res*len; } void dfs(int pa,int pb,int pc) { if(pa|pb|pc) { LL res=Find(pa+pb+pc); // for(int i=1;i<=pa+pb+pc;i++) printf("%c",loop[i]); //printf("%lld\n",res); // puts(""); ans=max(ans,res*res/(pa+pb+pc)); } if(pa<2) { loop[pa+pb+pc+1]='a'; dfs(pa+1,pb,pc); } if(pb<2) { loop[pa+pb+pc+1]='b'; dfs(pa,pb+1,pc); } if(pc<2) { loop[pa+pb+pc+1]='c'; dfs(pa,pb,pc+1); } return; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&N); scanf("%s",s+1); ans=0; int cnta=0,cntb=0,cntc=0; for(int i=1;i<=N;i++) { if(s[i]=='a') cnta++; else if(s[i]=='b') cntb++; else cntc++; } cnta=max(max(cnta,cntb),cntc); ans=1ll*cnta*cnta; // printf("%lld\n",ans); dfs(0,0,0); printf("%lld\n",ans); } return 0; }