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