Codeforces Round 630 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dsu

greedy

implementation

strings

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. K-Complete Word

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputWord $$$s$$$ of length $$$n$$$ is called $$$k$$$-complete if

- $$$s$$$ is a palindrome, i.e. $$$s_i=s_{n+1-i}$$$ for all $$$1 \le i \le n$$$;
- $$$s$$$ has a period of $$$k$$$, i.e. $$$s_i=s_{k+i}$$$ for all $$$1 \le i \le n-k$$$.

For example, "abaaba" is a $$$3$$$-complete word, while "abccba" is not.

Bob is given a word $$$s$$$ of length $$$n$$$ consisting of only lowercase Latin letters and an integer $$$k$$$, such that $$$n$$$ is divisible by $$$k$$$. He wants to convert $$$s$$$ to any $$$k$$$-complete word.

To do this Bob can choose some $$$i$$$ ($$$1 \le i \le n$$$) and replace the letter at position $$$i$$$ with some other lowercase Latin letter.

So now Bob wants to know the minimum number of letters he has to replace to convert $$$s$$$ to any $$$k$$$-complete word.

Note that Bob can do zero changes if the word $$$s$$$ is already $$$k$$$-complete.

You are required to answer $$$t$$$ test cases independently.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t\le 10^5$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$, $$$n$$$ is divisible by $$$k$$$).

The second line of each test case contains a word $$$s$$$ of length $$$n$$$.

It is guaranteed that word $$$s$$$ only contains lowercase Latin letters. And it is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer, representing the minimum number of characters he has to replace to convert $$$s$$$ to any $$$k$$$-complete word.

Example

Input

4 6 2 abaaba 6 3 abaaba 36 9 hippopotomonstrosesquippedaliophobia 21 7 wudixiaoxingxingheclp

Output

2 0 23 16

Note

In the first test case, one optimal solution is aaaaaa.

In the second test case, the given word itself is $$$k$$$-complete.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/07/2023 06:05:57 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|