#include<fstream>
using namespace std;
const  int N = 1000005;
char s[N];
int pred[N];
int calculPred ()
{
    int i, k = 0;
    pred[1] = 0;
    for (i = 2; s[i]; i++)
    {
        while (k > 0 && s[i] != s[k + 1])
            k = pred[k];
        if (s[i] == s[k + 1])
            k++;
        pred[i] = k;
    }
    i--;
    while (i>0 && !(pred[i] != 0 && i % (i - pred[i]) == 0))
        i--;

    return i;
}
int main ()
{
    ifstream in ("prefix.in");
    ofstream out ("prefix.out");
    int n;
    in>>n>>ws;
    int i;
    for (i = 1; i <= n; i++)
    {

        in.getline (s + 1, N);
        out<<calculPred()<<"\n";

    }
    return 0;
}