Problem Description

Define the distance between two strings of the same length as the numbers of the positions where the characters differ in these two strings.

If two strings of the same length has a distance of no more than $k$, we call these two string satisfy $k-matching$.

Given a string $S$ of length $n$ and a integer $k$. For each $i \in [1, n - 1]$, split $S$ into substrings $A$ and $B$, while $A = S[1,i]$ and $B = S[i + 1, n]$. For all the string pairs formed by some non empty substring of $A$ and some non empty substrings of $B$, count the numbers of pairs satisfying $k-matching$.

Input

The first line contains an integer $T\ (T\leq 60)$, denoting the number of test cases.

For each test case, input two integers $n\ (2 \leq n\leq 3000)$ and $k\ (0 \leq k \leq 3000)$ for the first line.

The second line contains $n$ characters denoting the string $S$.

Guarantee that $S$ only contains lowercase letters and the sum of $n$ is no more than $20000$.

Output

For each test case, output $n - 1$ lines.

The $i$-th line contains only a integer denoting the number of the pairs for $i$.

3
4 0
jslj
6 1
abcazz
5 0
zzzzz

1
1
1
5
9
10
8
5
4
8
8
4