問題文

ある文字列を 2 回繰り返してできる文字列を、平方と呼びます。 たとえば、abcabc や abababab は平方ですが、 abc や ababab は平方ではありません。 なお、長さ 0 の文字列も、平方とみなすことにします。

ヘイホー君はある日、英小文字のみからなる文字列 S を、道端で拾いました。 平方が好きなヘイホー君は、 文字列 S に以下の操作を繰り返すことで、平方を得ようと考えました。

• 1 ≦ p ≦ |S| を満たす整数 p を選ぶ。その後、S の p 文字目を削除する。ここで、|S| は S の長さを表すものとする。

ヘイホー君が平方を得るために必要な操作回数の最小値を求めてください。

入力例1

8
abacbabc

出力例1

2

以下のように 2 回の操作を行うことで、abcabc という平方を得ることができます。

• 5 文字目を削除し、abacabc にする。
• 3 文字目を削除し、abcabc にする。

入力例2

8
abababab

出力例2

0

abababab は平方なので、一度も操作を行う必要はありません。

入力例3

5
abcde

出力例3

5

すべての文字を削除することで、長さ 0 の平方を得ることができます。

入力例4

26
codefestivaltwozeroonefive

出力例4

14

oefiveoefive という平方を得ることができます。