Рядок \textbf{P} називається \textit{префіксом} рядка \textbf{A}, якщо \textbf{A=PB}, де \textbf{P} або \textbf{B} можуть бути порожніми рядками. Рядок \textbf{P }є \textit{нетривіальним префіксом} рядка \textbf{A}, якщо \textbf{A=PB}, і при цьому ні \textbf{P}, ні \textbf{B} не порожні. Рядок \textbf{Q} називається \textit{періодом рядка} \textbf{A}, якщо \textbf{Q} -- нетривіальний префікс \textbf{A} і при цьому \textbf{A} -- префікс (але не обов'язково нетривіальний) рядка \textbf{QQ}. Наприклад, рядки \textbf{abab} та \textbf{ababab} є періодами рядка \textbf{abababa}. Максимальний період рядка \textbf{A} -- самий довгий з його періодів, або порожній рядок, якщо у \textbf{A} немає жодного періода. Наприклад, максимальний період рядки \textbf{ababab} -- \textbf{abab}, максимальний період рядка \textbf{abc} -- порожній рядок. Напишіть програму, яка знайде суму довжин максимальних періодів для усіх префіксів заданого рядка \textbf{A}. \InputFile У першому рядку вхідного файлу міститься одне ціле число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{1000000}) -- довжина рядка \textbf{A}. У другому рядку міститься послідовність з \textbf{k} маленьких букв англійського алфавіту -- рядок \textbf{A}. \OutputFile У єдиному рядку вихідного файлу виведіть ціле число -- суму довжин максимальних періодів кожного префікса рядка \textbf{A}.