Retransmisja
Limit pamięci: 64 MB
Bajtocka telewizja retransmituje ostatni mecz reprezentacji siatkarskiej tego kraju. Mecz będzie nadawany w tradycyjnym systemie: kilka akcji, przebitka do
studia (aby mogli się wypowiedzieć zaproszeni eksperci), znowu kilka akcji, znowu przebitka...
Z jednej strony telewizja chciałaby pokazać jak najwięcej akcji (im dłuższa trasmisja, tym więcej reklam), z drugiej strony bajtoccy kibice siatkówki nie
należą do cierpliwych: jeśli w którymś pokazanym fragmencie relacji drużyna Bajtocji będzie grała słabo, kibice zniechęcą się i przełączą telewizor na operę mydlaną.
Najlepiej wobec tego pokazać tylko część meczu – pewną liczbę takich spójnych fragmentów trasmisji, w których jest więcej wygranych piłek niż
przegranych.
Ile najwięcej akcji może pokazać telewizja, aby utrzymać uwagę kibiców?
Wejście
W pierwszym wierszu wejścia znajduje się liczba zestawów testowych ().
W każdym z kolejnych wierszy znajduje się opis jednego zestawu testowego.
Opis jednego zestawu to niepusty ciąg znaków W i P.
Poszczególne znaki oznaczają wyniki kolejnych akcji: W oznacza piłkę piłka wygrana, zaś P – piłkę przegraną przez drużynę Bajtocji.
Długość ciągu nie przekracza znaków.
Łączna długość pliku nie przekracza MB.
Wyjście
Twój program powinien wypisać na wyjście, dla każdego zestawu, jedną liczbę całkowitą — maksymalną liczbę akcji, które może pokazać telewizja zgodnie z podanymi zasadami.
Przykład
Dla danych wejściowych:
1
WPWPPPWWPWPWPPWP
poprawną odpowiedzią jest:
12
Wyjaśnienie do przykładu:
Można osiągnąć wynik 12 akcji, pokazując dwa spójne fragmenty: akcje 1-3 (2 wygrane i 1 przegrana) oraz 7-15 (5 wygranych i 4 przegrane).
Ograniczenia
W testach wartych łącznie co najmniej 45 punktów długość każdego meczu nie przekracza
akcji.
Autor zadania: Lech Duraj.