求一个字符串的最小表示法。
将字符串S倍长，从根走length(s)步所走路径即为最小表示法。
记所到达位置为x，则这个最小表示法的起点为a[x]-len(s)+1
const maxn=;
var T:longint;
nt:array[..maxn,'a'..'z'] of longint;
a,f:array[..maxn] of longint;
sum,last:longint;
s:ansistring;
procedure Sam_init;
begin
fillchar(nt,sizeof(nt),);
fillchar(a,sizeof(a),);
fillchar(f,sizeof(f),);
sum:=; last:=;
end;
procedure Sam_ins(i:longint);
var p,q,np,nq:longint;
ch:char;
begin
ch:=s[i];
p:=last; inc(sum); np:=sum; a[np]:=a[p]+; last:=np;
while (p<>-) and (nt[p][ch]=-) do begin nt[p][ch]:=np; p:=f[p]; end;
if p=- then f[np]:= else
begin
q:=nt[p][ch];
if a[p]+=a[q] then f[np]:=q else
begin
inc(sum); nq:=sum; a[nq]:=a[p]+;
nt[nq]:=nt[q]; f[nq]:=f[q];
f[q]:=nq; f[np]:=nq;
while (p<>-) and (nt[p][ch]=q) do begin nt[p][ch]:=nq; p:=f[p]; end;
end;
end;
end;
procedure dfs(now,len:longint);
var ch:char;
begin
if len= then
begin
writeln(a[now]-length(s) div +);
exit;
end;
for ch:='a' to 'z' do
if nt[now][ch]<>- then
begin
dfs(nt[now][ch],len-);
exit;
end;
end;
procedure main;
var i:longint;
begin
readln(s);
s:=s+s;
Sam_init;
for i:= to length(s) do Sam_ins(i);
dfs(,length(s) div );
end;
begin
readln(T);
while T> do begin dec(T); main; end;
end.