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 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`’].

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.

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).

Sample Input 1 | Sample Output 1 |
---|---|

3 cabacbc 2 aabaacad 1 aabaacad 2 |
6 5 7 |