#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]; vector<int>P[5]; int calc(int m,string T){ int lst=0,cnt=0; int p[3]={0,0,0}; while(1){ for(char ch:T){ while(p[ch-'a']<int(P[ch-'a'].size())&&P[ch-'a'][p[ch-'a']]<=lst)p[ch-'a']++; if(p[ch-'a']==int(P[ch-'a'].size()))return cnt; lst=P[ch-'a'][p[ch-'a']]; }cnt++; }return 0; } 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<=8;++m){ string T="";dfs(1,T); } } void slv(){ n=read();cin>>S;S=" "+S; P[0].clear(),P[1].clear(),P[2].clear(); up(i,1,n)P[S[i]-'a'].p_b(i); ll res=0; up(i,1,cnt){ if(int(T[i].size())>n)break; int m=T[i].size(); int ret=calc(m,T[i])*m; res=max(res,ret*1ll*ret/m); }cout<<res<<'\n'; } int main(){ init(); int t=read();while(t--)slv(); return 0; }