#include<bits/stdc++.h> #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 long long ll; const int maxn=1e5+10; inline ll read(){ ll 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,dp[maxn][10]; string S,T; ll res; int calc(){ 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); }int res=0; up(i,1,n)res=max(res,dp[i][m]); return res; }void dfs(int x){ if(x>m){ int ret=calc(); res=max(res,ret*1ll*ret/m); return; }up(ch,'a','c'){ T+=ch; dfs(x+1); T.pop_back(); } } void slv(){ n=read();cin>>S;S=" "+S;res=0; for(m=1;m<=8;++m){ T=" ";dfs(1); // if(n>1000&&m>=4)break; } cout<<res<<'\n'; }int main(){ // freopen("string.in","r",stdin); // freopen("string.out","w",stdout); int t=read();while(t--)slv(); // cout<<"time:"<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; fclose(stdin); fclose(stdout); return 0; }