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.