#include <fstream>
#include <cstring>
using namespace std;
const int N = 1000005;
char s[N];
int t, L[N], D[N];

inline int prefix(){
    int v, k, n = strlen(s), i, max = 0;
    int sol[100005],nr;
    L[1] = 0;
    for(i = 2; i <= n; ++i){
        k = L[i - 1];
        while(k && s[k] != s[i - 1])
            k = L[k];
        if(s[k] == s[i - 1])
            ++k;
        L[i] = k;
     //   printf("%d %d\n", i, k);
        v = i;
        nr = 0;
        while(v && 2 * L[v] > v && !D[v]) {
            sol[++nr] = v;
            v = L[v];
        }

        if(v)
        if(2 * L[v] == i || D[v]){
           D[v] = 1;
            for(; nr; --nr)
                D[sol[nr]] = 1;
            max = i;
        }
    }

    return max;
}

int main() {
    ifstream fin("prefix.in");
    ofstream fout("prefix.out");
    int i;
    fin >> t;
    for(i = 1; i <= t; ++i) {
        fin >> s;
        memset(D, 0, sizeof(D));
      //  printf("%s\n", s);
    fout <<  prefix() << '\n';;
    }

    return 0;
}