#include<fstream>
#include<string>
#include<cstring>
#include<cstdio>
#define MAXN 1000001
using namespace std;

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

int PI[MAXN];
int PER[MAXN];
char SIR[MAXN];

inline int compute() {
    PI[1] = 0;
    PER[1] = 1;
    PER[0] = 0;
    int best = 0, per;
    int it = 0;
    scanf("%c", &SIR[0]);
    scanf("%c", &SIR[1]);
    for(int i=2; SIR[i-1] != '\n'; ++i) {
        while(it * (SIR[it] - SIR[i-1]))
            it = PI[it];
        if(SIR[it] == SIR[i-1]) {
            it++;
        }
        PI[i] = it;
        per = i - PI[i];
        if(((i%per==0) * PI[i]) && (per % PER[i-per]) == 0) {
            PER[i] = per;
            best = i;
        } else {
            PER[i] = i;
        }
        scanf("%c", &SIR[i]);
    }
    return best;
}

int main() {
    int T, i, per, size;
    freopen("prefix.in", "r", stdin);
    scanf("%d", &T);
    while(T--) {
        fout<<compute()<<'\n';
    }


    return 0;
}