A string s is called an (k,l)-repeat if s is obtained by concatenating k>=1 times some seed string t with length l>=1. For example, the string

s = abaabaabaaba

is a (4,3)-repeat with t = aba as its seed string. That is, the seed string t is 3 characters long, and the whole string s is obtained by repeating t 4 times.

Write a program for the following task: Your program is given a long string u consisting of characters ‘a’ and/or ‘b’ as input. Your program must find some (k,l)-repeat that occurs as substring within u with k as large as possible. For example, the input string

u = babbabaabaabaabab

contains the underlined (4,3)-repeat s starting at position 5. Since u contains no other contiguous substring with more than 4 repeats, your program must output the maximum k.

Input

In the first line of the input contains H- the number of test cases (H <= 20). H test cases follow. First line of each test cases is n - length of the input string (n <= 50000), The next n lines contain the input string, one character (either ‘a’ or ‘b’) per line, in order.

Output

For each test cases, you should write exactly one interger k in a line - the repeat count that is maximized.

Example

Input:
1
17
b
a
b
b
a
b
a
a
b
a
a
b
a
a
b
a
b

Output:
4

/*<br /> 这个博客的后缀数组的RMQ写的相当快</p> <p>http://hi.baidu.com/fhnstephen/blog/item/870da9ee3651404379f0555f.html</p> <p>就拿这个当模板好了，仰慕博客主人<br /> */<br /> #include<math.h><br /> #include<stdio.h><br /> using namespace std;<br /> const int maxn=50010;<br /> const int inf=5000000;<br /> int w[maxn],wa[maxn],wb[maxn],wv[maxn];<br /> int sa[maxn],rank[maxn],height[maxn];<br /> int a[maxn],f[maxn][20],n,ft[maxn];<br /> int cmp(int *r,int a,int b,int l)<br /> {<br /> return r[a]==r[b]&&r[a+l]==r[b+l];<br /> }<br /> void da(int *r,int *sa,int n,int m)<br /> {<br /> int i,j,p,*x=wa,*y=wb,*t;<br /> for (i=0; i<m; i++) w[i]=0;<br /> for (i=0; i<n; i++) w[x[i]=r[i]]++;<br /> for (i=1; i<m; i++) w[i]+=w[i-1];<br /> for (i=n-1; i>=0; i--) sa[--w[x[i]]]=i;<br /> for (p=1,j=1; p<n; m=p,j*=2)<br /> {<br /> for (p=0,i=n-j; i<n; i++) y[p++]=i;<br /> for (i=0; i<n; i++) if (sa[i]>=j) y[p++]=sa[i]-j;<br /> for (i=0; i<m; i++) w[i]=0;<br /> for (i=0; i<n; i++) w[wv[i]=x[y[i]]]++;<br /> for (i=1; i<m; i++) w[i]+=w[i-1];<br /> for (i=n-1; i>=0; i--) sa[--w[wv[i]]]=y[i];<br /> for (t=x,x=y,y=t,x[sa[0]]=0,p=1,i=1; i<n; i++)<br /> x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;<br /> }<br /> return;<br /> }<br /> void cal(int *r,int *sa,int n)<br /> {<br /> int i,j,k=0;<br /> for (i=1; i<=n; i++) rank[sa[i]]=i;<br /> for (i=0; i<n; height[rank[i++]]=k)<br /> for (k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);<br /> return;<br /> }<br /> int nmin(int a,int b)<br /> {<br /> return a<b?a:b;<br /> }<br /> void rmq(int n)<br /> {<br /> int i,j;<br /> for (i=1; i<=n; i++)<br /> f[i][0]=height[i];<br /> for (j=1; j<20; j++)<br /> for (i=1; i+(1<<j)-1<=n; i++)<br /> f[i][j]=nmin(f[i][j-1],f[i+(1<<j-1)][j-1]);<br /> return;<br /> }<br /> int lcp(int a,int b)<br /> {<br /> int x=rank[a],y=rank[b];<br /> if (x>y)<br /> {<br /> int t=x;<br /> x=y;<br /> y=t;<br /> }<br /> x++;<br /> int t=ft[y-x+1];<br /> return nmin(f[x][t],f[y-(1<<t)+1][t]);<br /> }<br /> int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> int i,testcase=0;<br /> char x;<br /> for (i=0; i<maxn; i++) ft[i]=int(double(log(i))/log(2.00));<br /> scanf("%d/n",&testcase);<br /> while (testcase--)<br /> {<br /> scanf("%d/n",&n);<br /> for (i=0; i<n; i++)<br /> {<br /> scanf("%c/n",&x);<br /> a[i]=x;<br /> }<br /> a[n]=0;<br /> da(a,sa,n+1,128);<br /> cal(a,sa,n);<br /> rmq(n);<br /> int k,max=0,r=0,t;<br /> for(int l=1; l<n; l++)//枚举长度<br /> for(int i=0; i+l<n; i+=l)<br /> {<br /> k=lcp(i,i+l);<br /> r=k/l+1;//注意为什么是k/l+1<br /> t=i-(l-k%l);<br /> if (t>=0&&k%l!=0)<br /> if (lcp(t,t+l)>=k) r++;<br /> if (r>max)<br /> max=r;<br /> //printf("l=%d r=%d i=%d i+l=%d/n",l,r,i,i+l);<br /> }<br /> printf("%d/n",max);<br /> }<br /> return 0;<br /> }<br />