You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给定一个只包含 $1\sim 9$ 的字符串 $s$。把 $s$ 划分为若干个非空字符串 $s_1,s_2,\dots,s_t$（$t$ 是偶数，是由你决定的），我们在纸上依次写下 $s_1$ 个 $s_2$，$s_3$ 个 $s_4$，以此往复。

• 比如 $s=\tt 123321$ 划分为 $\tt1,23,3,21$。那么我们会写下：$\tt 23212121$。

定义 $f(s)$ 表示上述划分后得到字符串的最小长度。

给一个长度为 $n$ 的字符串，对每一个长度为 $k$ 的字串，求其 $f$ 的值。

输入格式

第一行一个正整数 $T$ 表示数据组数。

每个测试点，第一行两个正整数 $n,k$。

接下来一个长度为 $n$ 的字符串表示 $s$。

输出格式

对每个测试点，输出一行 $n-k+1$ 个正整数表示 $f(s[i,i+k-1])$。

样例 #1

【样例输入】

3
4 4
5999
10 3
1111111111
11 4
49998641312

【样例输出】

14 
2 2 2 2 2 2 2 2 
12 18 17 15 12 7 7 2

样例 #2

见下发 $\textit{ex\_split2.in/ans}$。

该数据满足测试点 $2$ 的性质。

数据范围

对于所有数据，$T\leq 100$，$2\leq k\leq n\leq 2\times 10^5$。