Problem Description

If a string $S$ can be obtained exactly by repeating some string $K$ times, then we call $S$ a $K$-times repeated string. For example, abcabcabc can be seen as repeating abc for $3$ times, so abcabcabc is a $3$-times repeated string.

Similarly, aaaaaa is a $2$-times repeated string, a $3$-times repeated string, and also a $6$-times repeated string.

Now given a string $S$, please compute the minimum number of characters that need to be modified so that $S$ becomes a $K$-times repeated string.

Input Format

The first line contains an integer $K$.

The second line contains a string $S$ consisting only of lowercase letters.

Output Format

Output an integer as the answer. If $S$ cannot be modified into a $K$-times repeated string, output $-1$.

2
aabbaa

2

Hint

Constraints: $1 \le K \le 10^5$, $1 \le |S| \le 10^5$. Here $|S|$ denotes the length of $S$.

Lanqiao Cup 2020 National Contest Group C, Problem G.

Translated by ChatGPT 5