D. 子串
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

一个长度为$$$n$$$的仅包含小写字母的字符串，你需要找到两个不相交的非空子串，保证子串中的各字母出现次数均不超过$$$m$$$，求两个子串长度之和的最大值。

其中子串是指对于字符串$$$S=s_1~s_2~\cdots~s_n$$$，取一个区间$$$[l,r],~l \le r$$$，字符串 $$$s_l~s_{l+1}~\cdots~s_r$$$ 叫做字符串$$$S$$$的子串。

子串不相交是指这两个子串没有重叠的部分。

Input

第一行是一个正整数 $$$T~(1\le T\le 10^3)$$$，表示样例组数，以后是$$$T$$$组样例的输入。

对于每组样例：

第一行包含两个正整数 $$$n~(2 \le n \le 10^6)$$$ 和 $$$m~(1 \le m \le n)$$$；第二行是一个长度为$$$n$$$的仅包含小写字母的字符串。

输入保证 $$$\sum n \le 10^6$$$。

Output

依次输出每组样例的结果，为一行，仅包含一个整数，表示答案。

Example
Input
3
2 1
ab
5 1
ababa
10 2
ababababab
Output
2
4
8