L. Дописать в начало

Сколько символов нужно дописать в начало строки, чтобы она стала палиндромом?

Рассуждение зеркально классной задаче: ответ — это $n$ минус длина наибольшего префикса-палиндрома.

Стоит проверить это на примере. У строки aacecaaa наибольший палиндромный префикс — aacecaa длины 7, значит достаточно дописать одну букву: aaacecaaa.

Если решать через склейку, порядок будет $s + \# + R$, как в классной задаче про палиндромный префикс.

Одна строка длины $n$ ($1 \le n \le 10^6$) из строчных латинских букв.

Одно число — минимальное количество дописываемых в начало символов.