Squared Words

Time limit1sMemory limit128 MB

Summary

Given a lowercase string, delete the fewest letters so the remaining letters, in order, form a squared word xx.

Level: Medium7 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

A squared word is a word of the form $xx$ , that is, some string of letters written twice in a row. For example, the English words couscous, murmur (a low, continuous sound), tartar (hardened dental plaque), and hotshots are squared words.

Given a word, you may delete some of its letters so that what remains is a squared word. The result does not have to be a real English word. Deleting letters keeps the remaining letters in their original order. Find the minimum number of letters that must be deleted.

Input

The first line contains an integer $n$ ( $1 \le n \le 1000$ ), the length of the word. The second line contains a word made of $n$ lowercase English letters.

Output

Print a single integer: the minimum number of letters that must be deleted so that the word becomes a squared word. The empty word counts as a valid squared word.

Hint

For example, deleting y, s, o, s, k, o, and p from tachystoskopach leaves the squared word tachtach. (In Polish, tachtach is a little-known kind of coach.)

Examples3

Example 1
Input
```
15
tachystoskopach
```
Expected output
```
7
```
Example 2
Input
```
8
couscous
```
Expected output
```
0
```
Example 3
Input
```
3
abc
```
Expected output
```
3
```