Gizli parol
Bəzən proqramçılar parollarını çox maraqlı üsullarla gizlədirlər. Məsələn, Bill "Hacker" Gates-in parolunu necə gizlətdiyinə nəzər salaq. Bill uzunluğu L olan latın hərflərindən ibarət S adlı bir sıra seçir. Sonra, o, bütün L-1 təkhərfli dövri sola sürüşmələri həyata keçirir və parol olaraq yaranan sıraların (o cümlədən S) leksikoqrafik olaraq ən kiçik prefiksini seçir. Məsələn, alabala sırasını nəzərdən keçirək. Təkhərfli dövri sola sürüşmələr (ilk sıra daxil olmaqla) belə görünür:
alabala
labalaa
abalaal
balaala
alaalab
laalaba
aalabal
və leksikoqrafik olaraq birinci olan sıra aalabal-dır. Bu sıranın ilk hərfi ilkin sıranın 6 mövqeyində yerləşir (sıralardakı mövqelər 0-dan başlayaraq nömrələnir).
Verilən sıra S üçün leksikoqrafik olaraq ən kiçik sol dövri sürüşmənin başlanğıc mövqeyini tapacaq proqram yazın. Əgər leksikoqrafik olaraq ən kiçik sürüşmə bir neçə dəfə rast gəlinirsə, bu mövqelərdən ən kiçiyini çıxarın.
Giriş verilənləri
Birinci sətir testlərin sayını t ehtiva edir. Hər testin birinci sətiri giriş sırasının uzunluğunu l (5 ≤ l ≤ 100000) və ikinci sətir isə sıranın özünü s ehtiva edir.
Çıxış verilənləri
Hər test üçün dəqiq olaraq t sətir çıxarın. Hər sətirdə axtarılan başlanğıc mövqeyini çıxarın.