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 letters, forming a string , then a number . The koalas don't understand the meaning of , so they rearrange the letters of to look for a clue. To start off, for each permutation of , they give it a score , with 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 is just the minimum score of across all permutations of !

Now that the koalas know the rule, they devise a game. They will listen to the witch's string and predict 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

All characters in string are lowercase English letters.

#### Input Specification

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

The second line contains the string .

#### Output Specification

Output an integer , the minimum score of across all permutations of .

#### 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 palindromic substrings. It can be proven that this number is minimal.

#### Sample Input 2

```
20
whentheimposterissus
```

#### Sample Output 2

`8`

## Comments

AMOGUS

whentheimposterissus

I love how a simple observation drastically simplifies the time complexity from way too big for 2 seconds to linear!

Why can't you split

`dababy`

into`dab`

and`aby`

, giving no palindromes?All of the strings you split into need to be palindromes. Splitting into

`dab`

and`aby`

is invalid since neither are palindromes.Thanks, solved!

I don't even want to imagine a koala muttering "whentheimposterissus". Would defenitely be... interesting

this problem is sus