The koalas are having fun together at the annual Easter festival. Unfortunately, their festival is interrupted by the muttering of a strange koala witch. The koalas don't understand at first, but they eventually notice a pattern. The witch mutters ~N~ letters, forming a string ~S~, then a number ~X~. The koalas don't understand the meaning of ~X~, so they rearrange the letters of ~S~ to look for a clue. To start off, for each permutation of ~S~, they give it a score ~Y~, with ~Y~ representing the minimal number of palindromic substrings this permutation can be split into. Note that each character in the permutation must belong to exactly one substring. After doing some calculations, the koalas notice that ~X~ is just the minimum score of ~Y~ across all permutations of ~S~!

Now that the koalas know the rule, they devise a game. They will listen to the witch's string and predict ~X~ before she says it herself. However, the koalas don't have the brain power to calculate this number and need you to find the answer for them!

A palindrome is a string that is the same as its reverse. For example, strings tacocat, noon, x, and bbbb are palindromes, while strings abab and osuhow are not.

Constraints

~1 \leq N \leq 10^6~

All characters in string ~S~ are lowercase English letters.

Input Specification

The first line contains the integer ~N~, the number of characters in string ~S~.

The second line contains the string ~S~.

Output Specification

Output an integer ~X~, the minimum score of ~Y~ across all permutations of ~S~.

Sample Input 1

6
dababy

Sample Output 1

2

Explanation for Sample 1

We arrange the above string into bybada and split it into byb and ada, giving us ~2~ palindromic substrings. It can be proven that this number is minimal.

Sample Input 2

20
whentheimposterissus

Sample Output 2

8