Dövrü sürüşmələr

Verilmiş s sıranı nəzərdən keçirək. s sıranın k (0 ≤ k < |s|) üzərində dövri sürüşməsi, s sıranın başlanğıcından k simvolunun silinməsi və onların eyni ardıcıllıqla sonuna əlavə edilməsi ilə əldə edilən sıradır.

Elə bir k tapmaq lazımdır ki, s sıranın k üzərində dövri sürüşməsi leksikoqrafik olaraq minimal olsun. Əgər belə k bir neçədirsə, onların arasında ən kiçik k tapılmalıdır.

Giriş verilənləri

Birinci sətirdə bir ədəd - testlərin sayı m (1 ≤ m ≤ 20) verilir. Sonra m sətir verilir, hansı ki, 33 ilə 126 arasında kodlara malik simvollardan ibarətdir. Giriş faylının ölçüsünün 90 kilobaytdan çox olmadığı təmin edilir.

Çıxış verilənləri

Hər bir sətir üçün axtarılan k çıxarın.

Nümunələr