Строка P называется префиксом строки A, если A=PB, где P или B могут быть пустыми строками. Строка P является нетривиальным префиксом строки A, если A=PB, и при этом ни P, ни B не пустые. Строка Q называется периодом строки A, если Q – нетривиальный префикс A и при этом A – префикс (но не обязательно нетривиальный) строки QQ. К примеру, строки abab и ababab являются периодами строки abababa.
Максимальный период строки A – самый длинный из ее периодов, либо пустая строка, если у A нет ни одного периода. К примеру, максимальный период строки ababab – abab, максимальный период строки abc – пустая строка.
Напишите программу, которая найдет сумму длин максимальных периодов для всех префиксов заданной строки A.
В первой строке входного файла содержится одно целое число k (1 ≤ k ≤ 1000000) – длина строки A. Во второй строке содержится последовательность из k маленьких букв английского алфавита – строка A.
В единственной строке выходного файла выведите целое число – сумму длин максимальных периодов каждого префикса строки A.