#include <fstream>

using namespace std;

ifstream f("prefix.in");
ofstream g("prefix.out");

char sir[1000005];
int pre[1000005] , t;

int main()
{
    f >> t;
    f.getline(sir + 1 , 1000005 + 2);
    for(; t; --t)
    {
        f.getline(sir + 1 , 1000005 + 2);
        int k = 0 , i , result = 0;
        pre[1] = 0;

        for(i = 2; sir[i]; ++i)
        {
            while(k && sir[k + 1] != sir[i])
                k = pre[k];
            if(sir[k + 1] == sir[i])
                k++;
            pre[i] = k;
        }

        for(; i; i--)
            if(pre[i] << i >= i && pre[i] % (i - pre[i]) == 0)
                result = i , i = 1;

        g << result << "\n";
    }


    return 0;
}