#include<stdio.h>
#include<string.h>
#define MAX 20011
char arr[MAX];
int BoothAlgo(){
char lst[MAX];
int ans, i, j;
ans = 0;
int f[2*len];
for( i = 0; i < 2*len; ++i)
f[i] = -1;
for ( j = 1; j < 2*len; ++j) {
i = f[j-ans-1];
while( i != -1 && lst[j] != lst[ans+i+1]){
if( lst[i] < lst[ans+i+1] )
ans = j-i-1;
i = f[i];
}
if( i == -1 && lst[j] != lst[ans+i+1] ){
if( lst[j] < lst[ans+i+1] )
ans = j;
f[j-ans] = -1;
}
else
f[j-ans] = i+1;
}
return ans;
}
int main(){
int c;
while(c--){
printf("%d\n", BoothAlgo
()+1); }
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RyaW5nLmg+CiNkZWZpbmUgTUFYIDIwMDExCgpjaGFyIGFycltNQVhdOwoKaW50IEJvb3RoQWxnbygpewogICAgaW50IGxlbiA9IHN0cmxlbihhcnIpOwogICAgY2hhciBsc3RbTUFYXTsKICAgIHN0cm5jcHkobHN0LCBhcnIsIGxlbik7CiAgICBzdHJuY3B5KGxzdCtsZW4sIGFyciwgbGVuKTsKCWludCBhbnMsIGksIGo7CglhbnMgPSAwOwoJaW50IGZbMipsZW5dOwoJZm9yKCBpID0gMDsgaSA8IDIqbGVuOyArK2kpCgkJZltpXSA9IC0xOwoJZm9yICggaiA9IDE7IGogPCAyKmxlbjsgKytqKSB7CgkJaSA9IGZbai1hbnMtMV07CgkJd2hpbGUoIGkgIT0gLTEgJiYgbHN0W2pdICE9IGxzdFthbnMraSsxXSl7CgkJCWlmKCBsc3RbaV0gPCBsc3RbYW5zK2krMV0gKQoJCQkJYW5zID0gai1pLTE7CgkJCWkgPSBmW2ldOwoJCX0KCQlpZiggaSA9PSAtMSAmJiBsc3Rbal0gIT0gbHN0W2FucytpKzFdICl7CgkJCWlmKCBsc3Rbal0gPCBsc3RbYW5zK2krMV0gKQoJCQkJYW5zID0gajsKCQkJZltqLWFuc10gPSAtMTsKCQl9CgkJZWxzZQoJCQlmW2otYW5zXSA9IGkrMTsKCX0KICAgIHJldHVybiBhbnM7Cn0KCmludCBtYWluKCl7CiAgICBpbnQgYzsKICAgIHNjYW5mKCIlZCIsICZjKTsKICAgIHdoaWxlKGMtLSl7CiAgICAgICAgc2NhbmYoIiVzIiwgYXJyKTsKICAgICAgICBwcmludGYoIiVkXG4iLCBCb290aEFsZ28oKSsxKTsKICAgIH0KICAgIHJldHVybiAwOwp9Cgo=