Masala #M078B

Komiljon hozirgina uzunligi \(n\) ga teng va faqatgina ‘T’ va ‘M’ harflaridan tuzilgan \(s\) satrini topib oldi. Komiljon \(TTMT\) satrini yaxshi satr deb hisoblagani sababli, \(s\) dagi yaxshi satrlar sonini maksimallashtirmoqchi. Satrdagi \(TTMT\) satrlarning soni \(s_is_{i+1}s_{i+2}s_{i+3} = TTMT\) shartini qanoatlantirgan \(i\) larning soniga tengdir.

Komiljon bitta amalda \(s\) satrining istalgan joyiga ‘T’ yoki ‘M’ satrlardan birini joylashtirishi mumkin. Bu amalni birinchi marta bajarish uchun badal olinmaydi, ammo ikkinchi marta bajarish uchun 1 tanga, uchinchi marta bajarish uchun 2 tanga va h.k. davom etadi.

Komiljonning umumiy kayfiyati, 

(natijaviy satrdagi \(TTMT\) lar soni) \(-\) (jami to'lagan tangalari soni)

ga teng. Sizga boshlang'ich \(s\) satrli ma'lum, uning kayfiyatining maksimal qiymatini toping.

Birinchi qatorda bitta butun son - \(T\) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun, birinchi qatorda bitta butun son \(n(1 \leq n \leq 2 * 10^5)\) \(s\) satr uzunligi kiritiladi.

Ikkinchi qatorda esa \(s\) satrining o'zi kiritiladi.

Har bir test uchun alohida qatoda Komiljon erishishi mumkin bo'lgan maksimal kayfiyatni chiqaring.