#include <bits/stdc++.h> using namespace std; #define int long long #define lson pos<<1 #define rson pos<<1|1 const int MAXN=100010,N=30,Mod=998244353; int t,n,a[MAXN],nx[MAXN][5],k[N],lst[5],ans;char tmp; void check(int m){ int now=0,p=0,len=0; while(now<=n){ now=nx[now][k[++p]]; p%=m; if(!p&&now<=n)len++; }/* for(int i=1;i<=m;i++){ cout<<k[i]; } cout<<" "; cout<<len*len*m<<endl;*/ ans=max(len*len*m,ans); return; } void dfs(int now,int la,int lb,int lc){ if(now>7||la==3||lb==3||lc==3)return; if(la*la<=now-1&&lb*lb<=now-1&&lc*lc<=now-1&&now-1)check(now-1); k[now]=1; dfs(now+1,la+1,lb,lc); k[now]=2; dfs(now+1,la,lb+1,lc); k[now]=3; dfs(now+1,la,lb,lc+1); } signed main(){ scanf("%lld",&t); while(t--){ans=0; scanf("%lld",&n);tmp=getchar(); for(int i=1;i<=n;i++){ tmp=getchar(); a[i]=tmp-'a'+1; } lst[1]=n+1;lst[2]=n+1;lst[3]=n+1; for(int i=n;i>=0;i--){ nx[i][1]=lst[1]; nx[i][2]=lst[2]; nx[i][3]=lst[3]; lst[a[i]]=i; } dfs(1,0,0,0); printf("%lld\n",ans); } return 0; }