Masala B

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.