N = strlen(Str);

//N = Str.length();

for(int i=0; i<N; i++){

P[0][i] = Str[i]-'.';

}

int cnt;

for(stp=1, cnt=1; cnt>>1 < N; stp++, cnt<<=1){

for(int i=0; i<N; i++){

L[i].nr[0] = P[stp-1][i];

L[i].nr[1] = i+cnt<N?P[stp-1][i+cnt]:-1;

L[i].p = i;

}

sort(L, L+N, mycmp);

for(int i=0; i<N; i++){

P[stp][L[i].p] = i>0 && L[i].nr[0]==L[i-1].nr[0] && L[i].nr[1]==L[i-1].nr[1]?P[stp][L[i-1].p]:i;

}

}

int k, ret = 0;

if(x==y)return N-x;

for(k=stp-1; k>=0 && x<N && y<N; k--){

if(P[k][x]==P[k][y]){

x+=1<<k, y+= 1<<k, ret+=1<<k;

}

}

return ret;

int initial_length = N/2;

for(int i=0; i<N; i++){

mapping[P[stp-1][i]] = i;

}

/*

/*

int position;

for(int i=0; i<N; i++){

if(mapping[i]<initial_length){

//cout<<"first is at "<<i<<" with value "<<mapping[i]<<endl;

position = i;

break;

}

}

//cout<<"position is ";

//myprint(mapping[position], strlen(Str));

//cout<<endl;

int ans = mapping[position];

for(int i=position+1; i<N; i++){

/*

int tmp = lcp(mapping[position], mapping[i]);

if(tmp>=initial_length){

ans = mapping[i];

continue;

}else{

break;

}

}

cout<<ans<<endl;

scanf("%d",&T);

//cin>>T;

int nothing;

char buf[MAXN];

while(T--){

Str[0] = '\0';

scanf("%d %s",&nothing, buf);

//Str = "";

//cin>>nothing>>Str;

strcat(Str, buf);

strcat(Str, buf);

//Str+=Str;

build_sa();

work();

}