Vicdansız sürücü

Siz Şarl de Qoll hava limanına gəldikdən sonra, Parisə qədər sizi aparmağı təklif edən qeyri-rəsmi bir sürücüyə "rəqabətə davamlı qiymətlər" təklif etdiyinə görə sadəlövhcəsinə razılaşdınız. Nəticə fəlakət oldu: qiymət çox yüksək olmaqla yanaşı, sürücü bu qiyməti əsaslandırmaq üçün səfəri lazım olduğundan daha uzun etdi.

Siz bu fırıldağı fərq etdiniz, çünki həmin yerdən bir neçə dəfə səyahət etmisiniz. Yaxşı yaddaşınız var, buna görə də fırıldaqçının sizi keçməyə məcbur etdiyi hər bir döngəni daxil olmaqla, izlədiyiniz yolu yaxşı yadda saxlaya bilirsiniz.

Hazırda siz bu sürücü ilə bağlı şikayət etmək üçün polis bölməsindəsiniz və zabit sizdən hekayənizi danışmağınızı xahiş edir. O, hətta sizdən yolunuzun bütün təfərrüatlarını danışmağınızı xahiş edir. Buna bir neçə saat daha itirmək istəmədiyiniz üçün qısa versiyanı təqdim etməyə qərar verirsiniz.

Tutaq ki, siz $A,B,C,D,A,B,C,D$ yerlərindən keçdiyinizi xatırlayırsınız. Bu halda zabitə "Mən $ABCD$ yolunu iki dəfə keçdim" demək daha yaxşıdır, nəinki "Mən $ABCDABCD$ yolunu keçdim". Yolunuz eyni ardıcıllıqla təkrarlanırdısa, bu, heç bir detalı qaçırmadan izahatı xeyli qısaldacaq.

Daha dəqiq desək, sizdən keçdiyiniz yerlərin siyahısını qəbul edən və bu yolun ən qısa sıxılmış formasının ölçüsünü qaytaran bir proqram yazmaq lazımdır. Belə sıxılmış yol ola bilər:

• keçdiyiniz bir yer, "atomik yol" adlanır;

• iki sıxılmış yolun birləşməsi;

• sıxılmış yolun təkrarı, yəni $(C{)}^n$. Bu o deməkdir ki, siz $C$ yolunu ardıcıl olaraq $n$ dəfə keçmisiniz.

Sıxılmış yolun ölçüsü onun içindəki atomik yolların sayına görə müəyyən edilir.

Giriş verilənləri

İki sətirdən ibarətdir:

• Birinci sətir bir tam ədəd $n(0<n\le 700)$ — yolun uzunluğunu ehtiva edir.

• İkinci sətir $n$ ölçüsündə bir sətir şəklində yolu ehtiva edir. Hər bir yer alfasayısal simvolla təsvir olunur: rəqəm ( ${}^{\prime }{0}^{\prime }$-dan ${}^{\prime }{9}^{\prime }$-a qədər), kiçik hərf ( ${}^{\prime }{a}^{\prime }$-dan ${}^{\prime }{z}^{\prime }$-ə qədər) və ya böyük hərf ( ${}^{\prime }{A}^{\prime }$-dan ${}^{\prime }{Z}^{\prime }$-ə qədər).

Çıxış verilənləri

Bir tam ədəd çıxarın — ən qısa sıxılmış yolun ölçüsü.

Nümunələr

Qeyd

Misal 1. Yolun ən qısa sıxılmış forması: $(((a{)}^{3}b{)}^2(c{)}^{2}d{)}^2$. İçindəki atomik yollar: $a,b,c$ və $d$. Buna görə də yolun ölçüsü $4$-ə bərabərdir.

Misal 2. Yolun ən qısa sıxılmış forması: $(a{)}^{2}ba$. İçindəki atomik yollar: $a,b$ və $a$. Buna görə də yolun ölçüsü $3$-ə bərabərdir.