枚举答案长度$L$，设$A$和$B$分别为第一个循环节和反串的第一个循环节。
1.坏点不在$A$，那么可以暴力匹配检验。
2.坏点不在$B$，那么把串翻转后不在$A$中，转化为1。
3.坏点在$A$和$B$的交里面，那么只要长度为$n-L+1$的前后缀相同，那么就存在长度为$L$的循环节。
通过扩展kmp和Hash快速判断即可，时间复杂度$O(dn\log n)$。
#include<cstdio>
const int N=200010,P=233;
int T,n,i,j,t,k,p,l,ans,g[N];char a[N];unsigned int pow[N],f[N];
inline void swap(char&a,char&b){char c=a;a=b;b=c;}
inline unsigned int hash(int l,int r){return f[r]-f[l-1]*pow[r-l+1];}
inline int min(int a,int b){return a<b?a:b;}
void solve(){
for(i=1;i<=n;i++)f[i]=f[i-1]*P+a[i];
for(g[i=0]=n;i<n-1&&a[i+1]==a[i+2];i++);
for(g[t=1]=i,k=2;k<n;k++){
p=t+g[t]-1,l=g[k-t];
if(k+l>p){
j=(p-k+1)>0?(p-k+1):0;
while(k+j<n&&a[k+j+1]==a[j+1])j++;
g[k]=j,t=k;
}else g[k]=l;
}
for(i=n;i;i--)g[i]=g[i-1];
for(i=1;i<ans;i++){
j=g[i+1];
if(j==n-i||g[i+2]>=n-i+1)ans=i;else{
j+=i+2,k=(j-2)/i*i+1,t=k+i;
if(t>n)t=n;
if(hash(j,t)!=hash(j-k,t-k)||g[t+1]<n-t)continue;
for(t++;t<=n;t+=i)if(g[t]<min(i,n-t+1))break;
if(t>n)ans=i;
}
}
}
int main(){
for(pow[0]=i=1;i<N;i++)pow[i]=pow[i-1]*P;
scanf("%d",&T);
while(T--){
scanf("%d%s",&n,a+1);
ans=n-1;
solve();
for(i=1;i<n-i+1;i++)swap(a[i],a[n-i+1]);
solve();
printf("%d\n",ans);
}
return 0;
}