#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    freopen("stringg.in","r",stdin);
    freopen("stringg.out","w",stdout);
    int k, t[100002], i, j,n, ok=0;
    char ac[100002];
    scanf("%d",&k);
    scanf("%d\n");
   // printf("%s",ac);
    while(--k>=0){
        gets(ac+1);
         //   printf("\n%s\n",ac);
        scanf("%d\n");
        n=strlen(ac+1);
           // printf("%d\n",n);
        t[1]=0;
        j=0;
        for(i=2;i<=n;i++){
            while(j>0&&ac[j+1]!=ac[i])
                j=t[j];
            if(ac[j+1]==ac[i])
                j++;
            t[i]=j;}
       // for(i=0;i<n;i++)
       //     printf("%d",t[i]);
       ok=1;
        for(int i=n;i>=1;i--)
            if(t[i]&&i%(i-t[i])==0){
                ok=0;
                printf("%d\n",i);
                break;}
        if(ok==1) printf("0\n");}
    return 0;
}