#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=1,len=0; while(now<=n){ now=nx[now][k[p]]; if(now<=n){ len++; p=p%m+1; } } if(p!=1)len-=p-1; ans=max(len*len/m,ans); return; } void dfs(int now,int la,int lb,int lc){ if(now>6||la==3||lb==3||lc==3)return; if(la*la<now&&lb*lb<now&&lc*lc<now&&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; }