#include<cstdio>
const int N=1000000;
int prefix[N+1];
char s[N+1];
FILE*in,*out;
int t,n;
void scan(){
    fscanf(in,"%d",&t);
}
void init(){
    in=fopen("prefeix.in","r");
    out=fopen("prefeix.out","w");
    scan();
}
void closeFiles(){
    fclose(in);
    fclose(out);
}
void scanTest(){
    fgets(s,N+1,in);
}
void setPrefix(){
    int i,k=0;
    prefix[1]=0;
    for(i=2;i<=n;i++){
        while(k>0&&s[i]!=s[k+1])
            k=prefix[k];
        if(s[i]==s[k+1])
            k++;
        prefix[i]=k;
    }
}
void solve(){
    int i;
    setPrefix();
    for(i=1;i<=n;i++)
}
void shift(){
    int i;
    for(i=n;i>=1;i--)
        s[i]=s[i-1];
}
int stringLenght(char s[N+1]){
    int i=0;
    while(s[i]!='\0')
        i++;
    return i;
}
void initTest(){
    scanTest();
    n=stringLenght(s);
    shift();
}
int main(){
    init();
    while(t>0){
        t--;
        initTest();
        solve();
    }
    closeFiles();
    return 0;
}