Möhtəşəm alt sətirlər

Qoy S - ingilis əlifbasının böyük hərflərindən ibarət bir sıra olsun. Boş olmayan T sıraya S ilə əlaqəli k rütbəli mükəmməl deyilir, əgər k·T = T + T + ... + T (sıra T k dəfə təkrarlanır) S içində alt sıradır. Daha dəqiq desək, S = U + k·T + V, burada U və V bəzi (mümkün boş) sıralardır.

Sıra S verilir. S ilə əlaqəli x rütbəli mükəmməl sıra olan T mövcud olduğu ən böyük mümkün x rütbəsini tapın.

Giriş verilənləri

Yalnız ingilis əlifbasının böyük hərflərindən ibarət olan S (1 ≤ |S| ≤ 10^6) sırası.

Çıxış verilənləri

Bir ədəd çıxarın: S ilə əlaqəli mükəmməl sıranın maksimal rütbəsi.

Nümunələr