Нагадаємо, що паліндромом називається рядок, який читається однаково як зліва направо, так і праворуч наліво. Наприклад, паліндром є рядки «abba» і «madam».

Для довільного рядка \(s\) введемо операцію поділу навпіл, що позначається \(half(s)\). Значення \(half(s)\) визначається такими правилами:

• Якщо \(s\) не є паліндром, то значення \(half(s)\) не визначено;
• Якщо \(s\) має довжину 1, значення \(half(s)\) також не визначено;
• Якщо \(s\) є паліндромом парної довжини \(2m\), то \(half(s)\) — це рядок, що складається з перших \(m\) символів символів рядка \(s\);
• Якщо \(s\) є паліндромом непарної довжини \(2m+1\), більшої за 1, то \(half(s)\) — це рядок, що складається з перших \(m+1\) символів рядка \(s\).

Наприклад, значення \(half(inforamatics)\) та \(half(i)\) не визначені, \(half(аbbа) = ab\), \(half(madam) = mad\).

Паліндромність рядка \(s\) будемо називати максимальну кількість разів, яку можна застосувати до рядка \(s\) операцію поділу навпіл, щоб результат був визначений. Наприклад, паліндромність рядків «informatics» і «i» дорівнює 0, оскільки до них не можна застосувати операцію поділу навпіл навіть один раз. Паліндромність рядків «abba» і «madam» дорівнює 1, а паліндромності рядка «totottotot» дорівнює 3, коли операція поділу навпіл застосовна до неї три рази: «totottotot» -> «totot» -> «tot» -> «to».

Вказано деякий рядок \(s\). Необхідно змінити в ній мінімальну кількість символів так, щоб її паліндромність дорівнювала \(k\).

Формат вхідних даних

Перший рядок містить число \(k\) (\(0≤𝑘≤20\) ).

Другий рядок містить непустий рядок \(s\), що складається з малих літер латинського алфавіту. Її довжина не більша \(10^5\) символів.

Формат вихідних даних

У вихідний файл виведіть мінімальну кількість символів, яку потрібно змінити, або —1, якщо необхідним чином змінити рядок неможливо.

Приклад вхідних даних

2
abaabc

Приклад вихідних даних

1

Приклад вхідних даних

1
ababa

Приклад вихідних даних

1

Приклад вхідних даних

2
aa

Приклад вихідних даних

-1