#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("prefix.in");
ofstream fout("prefix.out");

const int maxLen = 1000005;
int pi[maxLen];
string s;

void solve()
{
    int maxPref = 0;
    fin >> s;
    s = "$" + s;
    cout << s << '\n';
    for(int i = 2; i < s.size(); i++)
    {
        int k = pi[i - 1];
        while(k && s[k + 1] != s[i])
            k = pi[k];
        if(s[k + 1] == s[i])
            k++;
        pi[i] = k;
        cout << i << ' ' << pi[i] << '\n';
        int p = i - pi[i];
        if(i != p && i % p == 0)
            maxPref = max(maxPref, i);
    }
    fout << maxPref << '\n';
}


int main()
{
    int nr_teste;
    fin >> nr_teste;
    while(nr_teste--)
        solve();
    return 0;
}