Visiting Marichka

Limits: 1 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka invited Zenik to her place to feed him, because she is worried about his sandwich-based diet. She prepared several dishes for him and allowed him to choose the order in which he will eat them. For this, she gave him a string \(s\) containing the first letters of the prepared dishes. For example, with dishes spaghetti and borsch, the string \(s\) will be equal to sb. Thus, to choose the order of the dishes, he needs to rearrange the letters in this string.

However, Zenik has only sandwiches on his mind, so he decided to rearrange the letters in such a way as to obtain the maximum possible number of substrings kanapka. He is interested in their maximum possible number; find this number.

Input

The first line contains a single integer \(n\) — the number of dishes prepared by Marichka.

The second line contains a string \(s\) of length \(n\) — the first letters of the prepared dishes.

Output

In a single line, print the answer — the maximum number of substrings kanapka that can be obtained by rearranging the characters of the given string.

Constraints

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

s consists exclusively of lowercase English letters,

5 points — a block of tests in which \(n \le 10\),

10 points — a block of tests in which the strings contain only the letters k, a, n, p,

10 points — a block of tests in which \(n \le 10^5\).

Samples

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

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

Notes

In the second example, by rearranging the letters, one can obtain the string vkkanapkanapkac.

Substrings kanapka:

vk kanapka napkac,

vkkanap kanapka c.