#include<iostream> #include<cstring> #include<map> using namespace std; #define int long long const int N=100100; int n; char s[N]; int f[N][3]; inline int id(char c){return c-'a';} void init(){ cin>>n; memset(s,0,(n+3)*sizeof(char)); scanf("%s",s+1); for(int c=0;c<3;c++){ int p=n+1; for(int i=n;i>=0;i--){ f[i][c]=p; if(id(s[i])==c)p=i; } } } int ans; int t[N]; void update(int len){ int nd=0,cnt=0,p=0; while(nd<=n){ nd=f[nd][t[++p]]; p%=len; if(!p&&nd<=n)cnt++; } ans=max(ans,cnt*cnt*len); } void dfs(int dep){ if(dep>8)return; for(int i=0;i<3;i++){ t[i]=i; update(dep); dfs(dep+1); t[i]=0; } } signed main(){ // freopen("string.in","r",stdin); // freopen("string.out","w",stdout); int T;cin>>T; while(T--){ init(); ans=n; dfs(1); printf("%lld\n",ans); } return 0; }