Втомленість та терпіння
Начатись у A0 не просто. Я дуже втомився. Зараз спекотно та душно, моя нога болить після учорашнього футболу, я не виспався і не зрозумів учора алгоритм Штора-Вагнера. Що гірше всього, зараз йде лекція, а я погано розумію те, що нам розповідають, і мені дуже хочеться спати. Щоб не провалитись в сон, я почав виписувати довгий рядок за наступним алгоритмом:
На першому кроці я записав рядок "a".
На i-му кроці (i ≥ 2) до рядка S, записаного на попередньому кроці, я дописав i-ту букву латинського алфавіту, а потім ще раз дописав рядок S.
Вже після чотирьох кроків я отримав рядок "abacabadabacaba" і збирався продовжити своє заняття, як раптом...
Я помітив на підлозі шматок паперу, на якому була написана дивно схожа послідовність букв. Може, це фрагмент рядка, який получиться після того, як я виконаю декілька кроків свого алгоритму? Невже колись давно на мому місці сиділо таке ж сумуюче ЛКШенятко, якому у голову прийшов точно такий же алгоритм? Якщо це так, то скільки ж корків попередник вспів зробити, до того як у нього закінчилось терпіння?
Вхідні дані
У першому рядку записано фрагмент рядка з рядкових латинських букв, записаний моїм попередником. Довжина фрагменту додатня і не перевищує 100000.
Вихідні дані
Виведіть єдине число - мінімальну кількість кроків алгоритму, яку повинен був виконати мій попередник, щоб у записаному ним рядку зустрічався такий фрагмент. Якщо я помилився, і фрагмент не можна отримати таким чином, виведіть "-1".