#include <stdio.h>
#include <string.h>
#define N 1000100

char A[1000001];
int p[1000001],max,n;

void prefix()
{
    int i,k=0;
    for (i=2; i<=n; i++)
    {
        while (k && A[k+1]!=A[i]) k=p[k];
        if (A[k+1]==A[i]) k++;
        p[i]=k;
        if (k && (i%(i-k)==0))
            if (i>max) max=i;
    }
}

int main()
{
FILE *in = fopen("prefix.in","r");
FILE *out= fopen("prefix.out","w");

int T;

fscanf(in,"%d",&T);

for (;T;T--)
{
fscanf(in,"%c",A[0]);
fscanf(in,"%s",A);
n = strlen(A);
for (int i=n;i;i--) A[i] = A[i-1];


max=0;
prefix();
fprintf(out,"%d\n",max);
}
}