Masala G

Sizga faqatgina A va B belgilaridan iborat bo'lgan satr berilgan, siz aynan bir marotaba satrning ixtiyoriy bo'sh bo'lmagan oralig'ini tanlashingiz kerak va oraliqdagi barcha A larni B ga, B larni esa A ga o'zgartirishingiz kerak. Sizning vazifangiz satrdagi A lar sonini maksimallashtirish.

Kirish faylining dastlabki satrida bitta butun son, $T(1 \le T \le 10)$ testlar soni kiritiladi. Keyingi $T$ ta satrda uzunligi $10^6$ dan katta bo'lmagan, tarkibi faqatgina A va B belgilaridan iborat satr kiritiladi. 

Har bir test uchun alohida qatorda, A belgilarining maksimal miqdorini chop eting.