Masala D

Husanboy “Algoritm Express” kompaniyasida kichik robot-kuryer Robo-1 ni sinovdan o‘tkazyapti. Robo-1 har daqiqada batareya holatini yozib boradi (to‘liq sikl n daqiqadan iborat):

• 'S' — robot quyosh panelidan quvvat oldi (batareya \(+1\)).
• 'M' — robot harakat qildi (batareya \(-1\)).

Sinov oxirida robot butun marshrutni aylana bo‘ylab aylanib chiqadi va yana boshlang‘ich joyiga qaytadi. Afsuski, jurnal saqlanayotgan paytda tizim buzilib, yozuvlar aylanma ko‘rinishda saqlanib qolgan: ya’ni sizda faqat \(n\) ta belgi bor, lekin qaysi daqiqadan boshlanganini bilmaymiz.

Siz istalgan k (1 ≤ k ≤ n) boshlanish daqiqasini tanlab, jurnalni quyidagicha o‘qiysiz:

\(S[k], S[k+1], ..., S[n], S[1], ..., S[k-1]\)

Husanboy robot haqiqiy startda batareyasi \(0\) bo‘lgan deb hisoblaydi. Tanlangan \(k\) to‘g‘ri start bo‘lishi uchun(ikkala shart ham bajarilishi majburiy):

1. O‘qish davomida batareya hech qachon manfiy bo‘lib ketmasin.
2. \(n\) daqiqadan so‘ng batareya yana \(0\) ga qaytsa.

Sizning vazifangiz: nechta \(k\) boshlanish daqiqasi to‘g‘ri ekanini toping.
 

Birinchi qatorda \(t\)— testlar soni beriladi. 
Har bir test uchun:

- Bir qatorda \(n (1 ≤ n ≤ 2⋅10^5)\)
- Keyingi qatorda uzunligi n bo‘lgan s satr (`'S'` va `'M'` belgilaridan iborat)

Cheklov: barcha testlar bo‘yicha n lar yig‘indisi \(≤ 2⋅10^5\).
 

Har bir test uchun bitta butun son chiqaring — mumkin bo'lgan boshlanishlar soni.