#include <iostream>
#include <fstream>
#include <cstring>
#define LMAX 1000005
using namespace std;
ifstream f ("prefix.in");
ofstream g ("prefix.out");
int pi[LMAX];
char s[LMAX];


void KMP ()
{
    int k = 0;
    pi[1] = 0;
    for (int i = 2; s[i]; i++)
    {
        while (k && s[k + 1] != s[i])
            k = pi[k];
        if (s[k + 1] == s[i])
            k++;
        pi[i] = k;
    }
}
int n;
int main()
{
    f>>n;
    s[0] = 'a';
    for (int i = 0; i < n; i++)
    {
        f>>(s + 1);
        cout<<s<<'\n';
        KMP();
        bool ok = false;
        for (int j = strlen(s + 1); j >= 1 && !ok; j--)
        {
            if (!pi[j]) continue;
            if (j % (j - pi[j]) == 0)
            {
                g<<j<<'\n';
                ok = true;
            }
        }
        if (!ok)
            g<<"0\n";
    }
    return 0;
}