Sətrin qüvvəti

$a$ və $b$ sətirlərinin birləşməsini $a\ast b$ ilə işarə edək.

Məsələn, əgər $a="abc"$ və $b="def"$, onda $a\ast b="abcdef"$.

Əgər sətirlərin birləşməsini vurma ilə sayarıqsa, onda qüvvətə yüksəltmə əməliyyatını növbəti şəkildə verə bilərik:

$a^0$ = “” (böş sətir)

$a^{n+1}=a\ast a^n$

Verilmiş $s$ sətrinə görə hər hansı bir $a$ sətri üçün $s=a^n$ olan $n$-in ən böyük qiymətini tapmaq lazımdır.

Giriş verilənləri

Hər bir test (əks olunan) çap simvollarını ehtiva edən yeganə $s$ sətrindən ibarətdir. $s$ sətri ən az bir, ən çox $10^6$ simvol ehtiva edir.

Çıxış verilənləri

Hər bir giriş $s$ sətri üçün ayrı sətirdə hər hansı bir a sətri üçün $s=a^n$ olan $n$-in ən böyük qiymətini verin.

Nümunələr