D. Palindrome Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob play exactly $$$k$$$ rounds on a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters. In each round, Alice first chooses to delete either the leftmost or the rightmost character of the current string. Bob then chooses one of the two ends of the remaining string and deletes the character at that end.

The final string has length $$$n-2k$$$. Its score is the number of palindromic substring occurrences. A substring is a contiguous sequence of characters, and a palindrome reads the same forwards and backwards. Single-character substrings count, and equal substrings at different positions are counted separately.

Alice wants to maximize the score, while Bob wants to minimize it. Both players see the current string and play optimally. Determine the final score.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\le T\le10^4$$$). The description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3\le n\le10^6$$$, $$$1\le k$$$, $$$2k \lt n$$$).

The second line contains a string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters.

For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print the final score under optimal play on a separate line.

Example
Input
8
6 1
xabbay
7 2
cababac
6 1
aaaaaa
5 1
abcba
3 1
abc
7 1
abababa
8 3
aaaabbbb
9 2
abacabcaa
Output
5
4
10
3
1
9
2
6
Note

In the first test case, $$$s=\texttt{xabbay}$$$ and $$$k=1$$$. The possible remaining strings of length $$$4$$$ are xabb, abba, and bbay, with palindromic substring counts $$$5,6,5$$$, respectively. Optimal play results in a score of $$$5$$$.