{9:05}
program prefix;
const fi='prefix.in';fo='prefix.out';
var pi:array[1..1000000]of longint;
    a:array[1..1000000]of char;
    f,g:text;
    i,j,t:longint;
function merge(leng,i:longint):boolean;
var j,k:longint;
    ok:boolean;
begin
ok:=true;j:=i;
repeat
k:=j-pi[j];
j:=pi[j];
if k<>leng then ok:=false;
until(j<=leng)or(not ok);
if j<leng then ok:=false;
merge:=ok;
end;

function calc_pref(n:longint):longint;
var k,q,sol:longint;
    i:longint;
    leng:longint;
begin
fillchar(pi,sizeof(pi),0);
k:=0;
pi[1]:=0;sol:=0;leng:=0;
for i:=2 to n do begin
     while(k>0)and(a[k+1]<>a[i])do k:=pi[k];
     if a[k+1]=a[i] then inc(k);
     pi[i]:=k;
     if(k>0)and(merge(i-pi[i],i)) then sol:=i;
    end;
calc_pref:=sol;
end;

begin
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
readln(f,T);
for i:=1 to T do begin
     j:=0;
     fillchar(a,sizeof(a),' ');
     while not seekeoln(f) do begin
            inc(j);
            read(f,a[j]);
           end;
     readln(f);
     writeln(g,calc_pref(j));
    end;
close(g);
closE(f);
end.