Annettuna on merkkijono, jonka jokainen merkki on A, B tai C. Saat poistaa joka askeleella kaksi vierekkäistä merkkiä, jotka eivät ole samat. Montako merkkiä voit poistaa enintään?

Esimerkiksi kun merkkijono on CABAC, voit poistaa enintään 4 merkkiä. Yksi optimaalinen ratkaisu on poistaa ensin merkit AB, jolloin merkkijonosta tulee CAC, ja sitten merkit CA, jolloin merkkijonosta tulee C.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Tämän jälkeen tulee t riviä, joista jokainen sisältää yhden merkkijonon. Merkkijonossa on n merkkiä ja jokainen merkki on A, B tai C.

Tuloste

Tulosta jokaisesta testistä, montako merkkiä voit poistaa enintään.

Esimerkki

Syöte:

4
AB
CABAC
AAAA
AABBCC

Tuloste:

2
4
0
6

Osatehtävä 1 (42 pistettä)

• 1 \le t \le 100
• 1 \le n \le 10

Osatehtävä 2 (58 pistettä)

• 1 \le t \le 100
• 1 \le n \le 100