8. Ešte nás vidíš?

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.