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

Autor zadania: Lech Duraj.