V izbe si spokojne žije na kope $n$ rôzne zafarbených ploštíc. Avšak, ich spokojné nažívanie prerušil príchod skupiny “Kynožíme Spolu Ploštice”, ktorá sa im nabúrala do ich domova a snaží sa ich zbaviť. Preto sa ploštice chcú skryť a byť nenápadné, v nádeji, že ich skupina nenájde.

Momentálne sú ploštice v jednom dlhom rade. Ploštice sú presvedčené, že čím viac homogénnejšie vyzerajú, tým skôr si ich nevšimnú. Preto by sa v rade chceli preorganizovať tak, že čo najmenej párov susediacich ploštíc má inú farbu.

Problém je, že ploštice a) nemajú čas na veľa presúvania a b) myslia centralizovane – centrálny mozog ploštíc vymyslí ako by sa mali pohybovať. Konkrétne, ploštice sa popresúvajú len v blokoch $k$ ploštíc, a každý takýto blok $k$ ploštíc sa presúva podľa rovnakého pravidla. Ako najlepšie sa vedia popresúvať?

Úloha

V izbe je vo veľkom rade usporiadaných $n$ ploštíc. Ploštice majú $26$ rôznych farieb (reprezentované písmenami a až z). Centrálny mozog ploštíc ich preusporiada nasledovne: najskôr si vyberie permutáciu $k$ prvkov (teda nejaké preusporiadanie $k$ pozícii), a nasledne podľa nej presporiadajú ploštice na poziciách $1$ až $k$, rovnako $k + 1$ až $2k$, a tak ďalej až po skupinu ploštíc na pozíciách $n-k+1$ po $n$ (môžete predpokladať že $n$ je deliteľné $k$). Permutácia je vybraná, aby minimalizovala počet susediacich dvojíc ploštíc s rôznymi farbami.

Koľko najmenej takýchto dvojíc vie centrálny mozog ploštíc dosiahnuť?

Formát vstupu

Na prvom riadku vstupu je číslo $k\geq 2$ - veľkosť permutovaných skupín ploštíc.

Na druhom riadku vstupu je reťazec zložený z písmen a-z reprezentujúci farby ploštíc v rade. Je garantované, že dĺžka reťazca je deliteľná $k$.

Formát výstupu

Vypíšte jediné číslo: najmenší počet susediacich dvojíc, ktoré vie centrálny mozog ploštíc dosiahnuť.

Hodnotenie

Existujú 4 sady vstupov. Vo všetkých z nich platí, že $k\leq 16$ a počet ploštíc nepresiahne $5000$. V polovici vstupov navyše platí, že $k\leq 5$ a počet ploštíc nepresiahne $1000$.

Príklad

Input:

4
abcabcabcabc

Output:

6

V tomto prípade sú skupiný ploštíc abca, bcab a cabc. Jedna z optimálnych permutácii je napríklad P = (2, 1, 4, 3), teda rad sa zmení z (abca)(bcab)(cabc) (zátvorky sú len na vizualizáciu ktoré ploštice sú spolu v skupine) na (baac)(cbba)(accb) – môžeme vidieť že je $6$ susediacich dvojíc rôznej farby

Input:

3
abcabcabcabc

Output:

11

Toto je rovnaký rad ploštíc ako v predchádzajúcom príklade, ale s $k=3$. Teraz ich nevie centrálny mozog ploštíc preorganizovať do lepšieho rozostavenia.