В гостях у Марічки

Limits: 1 sec., 256 MiB

Марічка запросила Зеника до себе додому, щоб погодувати його, бо переживає за його канапковий раціон. Вона приготувала йому декілька страв і дозволила йому вибрати порядок в якому він буде їх їсти. Для цього вона дала йому рядок \(s\), що містить перші букви приготованих страв. Наприклад, зі стравами spaghetti і borsch рядок \(s\) буде рівний sb. Отже, аби вибрати порядок страв, йому необхідно переставити букви в цьому рядку.

Але в Зеника одні канапки на думці, тому він вирішив переставити букви у такий спосіб, аби отримати якнайбільшу кількість підрядків kanapka. Його цікавить їх максимальна можлива кількість, знайдіть це число.

Input

У першому рядку задано одне ціле число \(n\) — кількість страв, приготованих Марічкою.

У другому рядку задано рядок \(s\) довжиною \(n\) — перші букви приготованих страв.

Output

У єдиному рядку виведіть відповідь — максимальну кількість підрядків kanapka, яку можна отримати переставивши символи заданого рядка.

Constraints

\(1 \le n \le 10^5\),

s складається виключно з малих літер англійського алфавіту,

5 балів — блок тестів в якому \(n \le 10\),

10 балів — блок тестів в яких рядки містять лише букви k, a, n, p,

10 балів — блок тестів в якому \(n \le 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
10 akcnxapazk	1

Input (stdin) сopy	Output (stdout) сopy
15 pkakvkcaapanank	2

Notes

У другому прикладі переставивши букви можна отримати рядок vkkanapkanapkac.

Підрядки kanapka:

vk kanapka napkac,

vkkanap kanapka c.