Merkkijonon jokainen merkki on A tai B. Voit muuttaa merkkijonoa tekemällä siirtoja, joissa vaihdetaan kaksi merkkiä keskenään.

Tehtäväsi on järjestää merkit niin, että ensin tulevat kaikki A-merkit ja sitten kaikki B-merkit. Montako siirtoa tarvitset vähintään?

Esimerkiksi kun merkkijono on BBAAB, siirtoja tarvitaan vähintään $2$. Yksi ratkaisu on BBAAB $\rightarrow$ ABBAB $\rightarrow$ AABBB.

Syöte

Ensimmäisellä rivillä on kokonaisluku $t$: merkkijonojen määrä.

Kullakin seuraavalla rivillä on merkkijono, jonka jokainen merkki on A tai B.

Tuloste

Tulosta kunkin merkkijonon pienin siirtojen määrä omalle rivilleen.

Esimerkki

Syöte:

5
AABA
AAABBB
BB
BBAAB
BAABABBBBBABABB

Tuloste:

1
0
0
2
2

Arvostelu

Koodiasi testataan syötteellä, jossa $t=1000$ ja kunkin merkkijonon pituus on enintään $100$. Saat tehtävästä $100$ pistettä, jos koodisi antaa oikean vastauksen kaikille merkkijonoille.