Şüşə muncuqlar
Bir aktrisa var idi. Bildiyiniz kimi, o, ən çox antik komediyalarda rol almağı sevirdi. Hamı onu sevirdi, lakin o, izdihamla maraqlanmırdı. Onun ən böyük hobbilərindən biri müxtəlif növ muncuqlarla məşğul olmaq idi. Bir çox muncuq istehsalçıları onun üçün hər gün yeni boyunbağılar və bilərziklər hazırlayırdılar. Bir gün o, əsas muncuq müfəttişinə zəng edərək çox uzun və xüsusi bir boyunbağı istədiyini bildirdi.
Boyunbağı müxtəlif ölçülü şüşə muncuqlardan hazırlanmalı idi və bir-birinə bağlı olmalı idi. Lakin heç bir ip muncuqlardan keçməməli idi - istənilən anda istənilən muncuğu ayırmaq mümkün olmalıdır. Aktrisa muncuqların ardıcıllığını seçdi və onlardan boyunbağı düzəltmək istədi. Lakin sonra bir problem olduğunu anladı. İki qonşu muncuq arasındakı əlaqə çox etibarlı deyildi, buna görə boyunbağı öz ağırlığı altında qırıla bilərdi. Vəziyyət daha da pisləşir, əgər boyunbağı hissələrə ayrılarsa. Muncuqların birləşmə nöqtələri çox vacibdir. Əgər kiçik muncuqlar əvvəlindədirsə, boyunbağının qırılma ehtimalı daha yüksəkdir, nəinki orada böyük muncuqlar olsaydı. Muncuq istehsalçısı boyunbağının etibarlılığını yoxlamaq istəyir və boyunbağının qırılma ehtimalının ən yüksək olduğu nöqtəni müəyyən edə biləcək bir proqram tələb edir.
Boyunbağı A = a_1a_2 ... a_m ardıcıllıqla verilir, bu, muncuqların ölçülərini təsvir edir. Boyunbağı bağlıdır, buna görə a_m muncuğundan sonra a_1 muncuğu gəlir.
Birləşmə nöqtəsi i nöqtəsi j nöqtəsindən daha pis hesab olunur, əgər və yalnız A[i] = a_ia_{i+1}...a_na_1...a_{i-1} ardıcıllıqla A[j] = a_ja_{j+1}... a_na_1...a_{j-1} ardıcıllıqla leksikoqrafik olaraq kiçikdirsə. a_1a_2...a_n ardıcıllıqla b_1b_2...b_n ardıcıllıqla leksikoqrafik olaraq kiçikdir, əgər elə bir tam i (i ≤ n) mövcuddur ki, a_j = b_j hər bir j üçün (1 ≤ j < i və a_i < b_i).
Giriş verilənləri
Birinci sətir testlərin sayını N ehtiva edir. Hər bir test boyunbağının strukturunu təsvir edən bir sətirlə verilir. Boyunbağının maksimal uzunluğu 10000 simvoldur. Hər bir muncuq kiçik hərflərlə latın əlifbasının simvolu ilə təmsil olunur (a-z), burada a < b...z.
Çıxış verilənləri
Hər bir test üçün ayrı bir sətirdə bir tam ədəd çıxarın - ilk qırılacaq muncuğun nömrəsi, yəni i elə ki, A[i] ardıcıllıqla leksikoqrafik olaraq bütün n mümkün boyunbağı ayrılmalarından ən kiçikdir. Əgər problem bir neçə həllə malikdirsə, onda i ən kiçik olanı çıxarın.