var s:array[1..1000000] of char;
pi:array[1..1000000] of longint;
t,contor,i,k,a,b,m,q,j,ln,lmax:longint;
f,g:text;
begin
assign(f,'prefix.in');
assign(g,'prefix.out');
reset(f);rewrite(g);
readln(f,t);
for contor:=1 to t do
    begin
    for i:=1 to b do
        s[i]:=#0;
    readln(f,s);
    lmax:=0;
    a:=1;b:=1000000;
    while a<=b do
          begin
          m:=a+(b-a) div 2;
          if s[m]=#0 then
             b:=m-1
          else
              a:=m+1;
          end;
    pi[1]:=0;
    k:=0;
    i:=2;
    while s[i]=s[1] do
          i:=i+1;
    if i>2 then
       lmax:=i-1;
    for i:=2 to b div 2 do
        begin
        while (k>0) and (s[k+1]<>s[i]) do
              k:=pi[k];
        if s[k+1]=s[i] then
           k:=k+1;
        pi[i]:=k;
        q:=0;a:=1-i;
        ln:=0;
        for j:=1 to b do
            begin
            while (q>0) and ((s[q+1]<>s[j]) or (q+1>i)) do
                  q:=pi[q];
            if (s[q+1]=s[j]) and (q<i) then
               q:=q+1;
            if q=i then
               if j-i+1=a+i then
                  begin
                  ln:=ln+i;
                  a:=j-i+1;
                  end
               else
                   begin
                   if j-i+1>a+i then
                      break;
                   end
            else
                if j mod i=0 then
                   break;
            end;
        if (ln>lmax) and (ln<>i) then
           lmax:=ln;
        end;
    writeln(g,lmax);
    end;
close(f);close(g);
end.