Word $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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\ninput = sys.stdin.readline\nfrom collections import defaultdict\n\nclass Unionfind:\n    def __init__(self, n):\n        self.par = [-1]*n\n        self.rank = [1]*n\n    \n    def root(self, x):\n        r = x\n        \n        while not self.par[r]<0:\n            r = self.par[r]\n        \n        t = x\n        \n        while t!=r:\n            tmp = t\n            t = self.par[t]\n            self.par[tmp] = r\n        \n        return r\n    \n    def unite(self, x, y):\n        rx = self.root(x)\n        ry = self.root(y)\n        \n        if rx==ry:\n            return\n        \n        if self.rank[rx]<=self.rank[ry]:\n            self.par[ry] += self.par[rx]\n            self.par[rx] = ry\n            \n            if self.rank[rx]==self.rank[ry]:\n                self.rank[ry] += 1\n        else:\n            self.par[rx] += self.par[ry]\n            self.par[ry] = rx\n    \n    def is_same(self, x, y):\n        return self.root(x)==self.root(y)\n    \n    def count(self, x):\n        return -self.par[self.root(x)]\n\nt = int(input())\n\nfor _ in range(t):\n    n, k = map(int, input().split())\n    s = input()[:-1]\n    uf = Unionfind(n)\n    \n    for i in range(n//2):\n        uf.unite(i, n-1-i)\n    \n    for i in range(n-k):\n        uf.unite(i, i+k)\n    \n    d = defaultdict(dict)\n    \n    for i in range(n):\n        if s[i] not in d[uf.root(i)]:\n            d[uf.root(i)][s[i]] = 1\n        else:\n            d[uf.root(i)][s[i]] += 1\n    \n    rs = set(uf.root(i) for i in range(n))\n    ans = 0\n    \n    for r in rs:\n        ans += uf.count(r)-max(list(d[r].values()))\n    \n    print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17689