#include<bits/stdc++.h> #pragma gcc optimize(2) #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxn=5e5+10,mod=998244353; inline int read(){ int x=0; short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m,cnt,dp[maxn][9]; string S; string T[305]; int calc(int m,string &T){ up(i,0,n)up(j,1,m)dp[i][j]=-1e9; dp[0][m]=0; up(i,1,n)up(j,1,m){ dp[i][j]=max(dp[i][j],dp[i-1][j]); if(S[i]==T[j])dp[i][j]=max(dp[i][j],dp[i-1][((j==1)?m:(j-1))]+1); }return dp[n][m]; } bool chk(string &P){ int c1=0,c2=0,c3=0; for(char ch:P){ if(ch=='a')c1++; else if(ch=='b')c2++; else if(ch=='c')c3++; if(max(max(c1,c2),c3)>=3)return 0; }return 1; } void dfs(int x,string &P){ if(x>m){ if(chk(P))T[++cnt]=P; return; }up(ch,'a','c'){ P+=ch; dfs(x+1,P); P.pop_back(); } } void init(){ for(m=1;m<=6;++m){ string T=" ";dfs(1,T); } } void slv(){ n=read();cin>>S;S=" "+S; ll res=0; up(i,1,cnt){ if(int(T[i].size())-1>n)break; int m=T[i].size()-1; int ret=calc(m,T[i]); res=max(res,ret*1ll*ret/m); }cout<<res<<'\n'; } int main(){ init(); int t=read();while(t--)slv(); return 0; }