Problem G
Magical String

Lajuk loves to play with magic, especially with a magical string.

A magical string consists of $N$ lowercase English characters which has no substring containing $3$ or more identical characters, e.g., “aabbaacbb”, “icpc”, “asia”, “singapore” are magical strings. On the other hand, “waaaah” and “singapooore” are not magical strings as they contain “aaaa” (in the first example) and “ooo” (in the second example).

We can convert any character in the magical string into any other character as long as the direct consequence of the conversion results in some substring containing $3$ or more identical characters. When this happens, that particular substring which contains identical characters of the maximum length will magically transform into an asterisk (‘*’) character. This is the reason why it is called a magical string.

For example, consider a magical string $S[1, 7] = $ “cabacbc”.

If we convert the third character (‘b’) into ‘a’, then the substring $S[2, 4]$ becomes “aaa” which contains $3$ identical characters. This substring is then transformed into an asterisk ‘*’ and the string becomes “c*cbc”.

Note that the asterisk character does not have any magical power, i.e. we cannot convert any asterisk character, and no asterisk character will ever be transformed (e.g., when there are $3$ consecutive asterisk characters, nothing happens). Basically, asterisk characters are dead.

Now, let’s move on to the fun part. Lajuk gives you a magical string $S$ and an integer $K$. Your task is to convert at most $K$ characters (one at a time) in the string such that the total number of characters which are transformed into asterisks is as large as possible.

In the example above (“cabacbc”), if $K = 2$, then the output is $6$, i.e. convert $S[3]$ from ‘b’ into ‘a’ ($3$ characters turn into an asterisk), and convert $S[6]$ from ‘b’ into ‘c’ ($3$ characters turn into an asterisk).

Input

Input begins with an integer $T (1 \le T \le 50)$ representing the number of cases. Each case contains a magical string $S (1 \le |S| \le 1\, 000)$ followed by an integer $K (1 \le K \le 1\, 000)$ (separated by a single space) in a line. The string $S$ contains only lowercase English characters [‘a’..‘z’].

Output

For each case, output in a line containing one integer representing the maximum number of characters in the given magical string which can be turned into asterisks by converting at most $K$ characters.

Explanation

For the second case in the sample input, convert $S[3]$ from ‘b’ into ‘a’. “aabaacad” $\rightarrow $ “aaaaacad” $\rightarrow $ “*cad” ($5$ characters turn into asterisks). For the third case in the sample input, convert $S[6]$ from ‘c’ into ‘a’. “aabaacad” $\rightarrow $ “aabaaaad” $\rightarrow $ “aab*d” ($4$ characters turn into asterisks). Then, convert $S[3]$ from ‘b’ into ‘a’. “aab*d” $\rightarrow $ “aaa*d” $\rightarrow $ “**d” ($3$ more characters turn into asterisks).

3
cabacbc 2
aabaacad 1
aabaacad 2

6
5
7