#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

int v[1000001];

int main()
{
    int T,mx,poz,sz;
    string s;
    f >> T;
    for(int q = 1; q <= T; q++){
        f >> s;
        s.insert(0, "b");
        mx = 0;
        poz = 0;
        sz = s.size();
        for(int i = 2,k = 0; i <= sz + 1; i++){
            while(k > 0 && (s[k + 1] != s[i]))
                k = v[k];
            if(s[k + 1] == s[i])
                k++;
            v[i] = k;
            if(v[i] > mx){
                mx = v[i];
                poz = i;
            }
        }
        int i = poz;
        while(v[i] != 0 && poz != 0)
            i--;
        if(i == 0)
            g << 0 << "\n";
        else
            g << poz - poz % i << "\n";
        for(int i = 1; i <= sz + 1; i++)
            v[i] = 0;
    }
    return 0;
}