Fişierul intrare/ieşire:	bouncer.in, bouncer.out	Sursă	ad-hoc
Autor	Ciprian Oprisa	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.5 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bouncer

Gigel s-a săturat să rezolve probleme de algoritmică, aşa că s-a angajat ca bouncer la cel mai recent club de fiţe din Cluj-Napoca. Rolul lui e să stea la intrare şi să decidă cine are voie să intre. Clubul e mare şi încăpător, dar şeful său i-a dat o sarcină foarte importantă. În nici un moment, diferenţa absolută dintre numărul de bărbaţi şi femei din club nu are voie să depăşească valoarea K.

În prima zi de lucru, Gigel observă că deja s-a format la intrare o coadă ce conţine N persoane. Pentru că Gigel face regulile, el a decis că poate să respecte regula "primul venit, primul servit", sau poate să folosească regula "al doilea venit, primul servit". Cu alte cuvinte, în orice moment Gigel poate lăsa să intre în club prima persoană aflată la coadă (caz în care a doua persoană trece pe prima poziţie, a treia persoană pe a doua, etc.) sau a doua persoană aflată la coadă (caz în care prima persoană din coadă îşi păstrează locul, a treia persoană trece pe a doua poziţie, etc.).

Atunci când nu mai poate lăsa persoane să intre în club conform celor două reguli, fără ca diferenţa absolută dintre numărul de bărbaţi şi numărul de femei să depăşească valoarea K, Gigel anunţă că s-a umplut clubul şi toată lumea rămasă la coadă pleacă acasă.

Gigel şi-ar dori să afle care este numărul maxim de persoane din coadă pe care le poate lăsa să intre în club.

Date de intrare

Fişierul de intrare bouncer.in conţine pe prima linie numărul de teste T. Fiecare test este format din două linii. Pe prima linie a fiecărui test se află numerele N şi K, reprezentând numărul de persoane aflate la coadă, respectiv diferenţa absolută maximă admisă dintre numărul de bărbaţi şi numărul de femei din club. Pe a doua linie a fiecărui test se află un şir de N caractere, format doar din literele 'B' şi 'F', reprezentând tipul de persoane aflate la coadă. Coada începe din stânga şirului.

Date de ieşire

În fişierul de ieşire bouncer.out se va tipări câte o linie pentru fiecare test, conţinând numărul maxim de persoane care pot fi lăsate să intre în club, conform regulilor.

Restricţii

• 1 ≤ T ≤ 40
• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ 100

Exemplu

Cum se trimit solutii?