记录编号	372267	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 寒假ing	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	1.342 s
提交时间	2017-02-18 08:53:43	内存使用	10.28 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=50000*2+500;
int Wa[maxn],Wb[maxn],Ws[maxn];
int cmp(int *r,int x,int y,int l)
{return r[x]==r[y] && r[x+l]==r[y+l];}
void da(int *r,int *sa,int n,int m){
	int i,j,p,*x=Wa,*y=Wb;
	for(i=0;i<m;i++) Ws[i]=0;
	for(i=0;i<n;i++) Ws[x[i]=r[i]]++;
	for(i=1;i<m;i++) Ws[i]+=Ws[i-1];
	for(i=n-1;i>=0;i--) sa[--Ws[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p){
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) Ws[i]=0;
		for(i=0;i<n;i++) Ws[x[y[i]]]++;
		for(i=1;i<m;i++) Ws[i]+=Ws[i-1];
		for(i=n-1;i>=0;i--) sa[--Ws[x[y[i]]]]=y[i];
		swap(x,y);x[sa[0]]=0;p=1;
		for(i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i],sa[i-1],j) ? p-1 : p++;
	}
}
int Rank[maxn],height[maxn];
void calc_height(int *r,int *sa,int n){
	int i,j,k=0;
	for(i=1;i<=n;i++) Rank[sa[i]]=i;
	for(i=0;i<n;height[Rank[i++]]=k)
		for(k ? k-- : 0 ,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
int n,sa[maxn],a[maxn];
int Log2[maxn],RMQ[18][maxn];
void RMQ_Init(){
	for(int i=2;i<=n;i++){
		Log2[i]=Log2[i-1];
		if((1<<Log2[i]+1)==i)Log2[i]++;
	}
	for(int i=1;i<=n;i++) RMQ[0][i]=height[i];
	int now=1;
	for(int j=1;j<=Log2[n];j++){
		for(int i=1;i<=n;i++){
			RMQ[j][i]=RMQ[j-1][i];
			if(i+now<=n)RMQ[j][i]=min(RMQ[j][i],RMQ[j-1][i+now]);
		}
		now<<=1;
	}
}
int RMQ_Ask(int s,int t){
	if(s>t)swap(s,t);s++;
	int k=Log2[t-s+1];
	int l=1<<k;
	return min(RMQ[k][s],RMQ[k][t-l+1]);
}
void Init();
int main(){
	freopen("broken.in","r",stdin);freopen("broken.out","w",stdout);
	int T=0;scanf("%d",&T);
	while(T--)Init();
	return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		char ch;scanf(" %c",&ch);
		a[i]=a[(n<<1)-i]=ch;
	}
	a[n]='$'+1;
	int len=n;
	n=(n<<1)+1;a[n]='$';
	da(a,sa,n+1,'z'+50);
	calc_height(a,sa,n);
	// for(int i=0;i<n;i++)printf("%c",a[i]);
	RMQ_Init();
	int ans=0;
	for(int i=1;i<=len;i++){
		int Max=0;
		for(int j=0;j+i<len;j+=i){
			int totlen=0;
			totlen+=RMQ_Ask(Rank[j],Rank[j+i]);
			totlen+=RMQ_Ask(Rank[n-1-j],Rank[n-1-i-j]);
			totlen--;
			Max=max(Max,totlen);
		}
		ans=max(ans,Max/i+1);
	}
	printf("%d\n",ans);
}