Magična niska se sasoji od $N$ malih slova Engleskog alfabeta, tako da u njoj ne postoje $3$ uzastopna ista karaktera. Na primer: $\texttt{aabbaacbb}$, $\texttt{ioi}$, $\texttt{azija}$, $\texttt{singapur}$ su magične niske. Za razliku od njih, niske $\texttt{staaaa}$ i $\texttt{singapuuur}$ nisu magične niske, jer sadrže $\texttt{aaaa}$ (u prvom primeru) i $\texttt{uuu}$ (u drugom primeru).

Možemo da pretvorimo bilo koje slovo u magičnoj nisci u bilo koji drugo slovo, sve dok je direktna posledica tog pretvaranja postojanje $3$ ili više uzastopna identična slova. Kada se ovo desi, skup uzastopnih identičnih slova najveće veličine se magično pretvori u karakter zvezdica: $\texttt{*}$.

Razmotrite, na primer, magičnu nisku $S[1, 7] =$ $\texttt{cabacbc}$.

Ako pretvorimo treći karakter u karakter $\texttt{a}$, onda karakteri na pozicijama $\{2,3,4\}$ postaju $\texttt{aaa}$ tj. $3$ uzastopna identična karaktera. Tada oni postaju zvezdica i nova niska glasi $\texttt{c*cbc}$.

Primetite da zvezdice nemaju magičnu moć, tj. nikada ne možemo pretvoriti zvezdicu u neki drugi karakter, niti će ikada neka zvezdica biti pretvorena u nešto drugo (ukoliko imamo $3$ ili više uzastopne zvezdice, ništa se ne dešava).

Dat je magična niska $S$ i broj $K$. Vaš zadatak je da pretvorite najviše $K$ karaktera (jedan po jedan) u nisci, tako da je broj karaktera koji su pretvoreni u zvezdice je najveći mogući.

U primeru iznad ($\texttt{cabacbc}$), ako $K = 2$, tad je izlaz $6$, tj. pretvorimo treći karakter iz $\texttt{b}$ u $\texttt{a}$ ($3$ karaktera postaju zvezdice), i pretvorimo šesti karakter iz $\texttt{b}$ u $\texttt{c}$ (još $3$ karaktera postaju zvezdice).

Opis ulaza

Ulaz počinje sa celim brojem $T (1 \le T \le 50)$ koji predstavlja broj test primera. Svaki test primer sadrži magičnu nisku $S (1 \le |S| \le 1\,000)$ za kojom sledi ceo broj $K (1 \le K \le 1\,000)$ u istoj liniji. Niska $S$ sadrži samo mala slova Engleskog alfabeta.

Opis izlaza

Za svaki test primer, u jednoj liniji ispisati jedan ceo broj, koji predstavlja najveći moguć broj karaktera u datoj magičnoj nisci koji se mogu pretvoriti u karaktere zvezdica, menjanjem najviše $K$ karaktera.

Primer ulaza

3
cabacbc 2
aabaacad 1
aabaacad 2

Primer izlaza

6
5
7

Objašnjenje primera

U drugom test primeru, promenimo treći karakter iz $\texttt{b}$ u $\texttt{a}$. $\texttt{aabaacad}$ $\rightarrow$ $\texttt{aaaaacad}$ $\rightarrow$ $\texttt{*cad}$ ($5$ karaktera postaju zvezdice). U trećem test primeru, promenimo šesti karakter iz $\texttt{c}$ u $\texttt{a}$. $\texttt{aabaacad}$ $\rightarrow$ $\texttt{aabaaaad}$ $\rightarrow$ $\texttt{aab*d}$ ($4$ karaktera postaju zvezdice). Onda, promenimo treći karakter iz $\texttt{b}$ u $\texttt{a}$. $\texttt{aab*d}$ $\rightarrow$ $\texttt{aaa*d}$ $\rightarrow$ $\texttt{**d}$ (još $3$ karaktera postaju zvezdice).