#include<fstream>
#include<string>
#include<cstring>
#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;
    fin>>SIR[0];
    fin>>noskipws>>SIR[1];
    for(int i=2; SIR[i-1] != '\n'; ++i, fin>>noskipws>>SIR[i-1]) {
        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;
        }
    }
    return best;
}

int main() {
    int T, i, per, size;
    fin>>T;
    while(T--) {
        fout<<compute()<<'\n';
    }


    return 0;
}