33ος ΠΔΠ Καμπ (κοινά)
CANDYSTRIPE (candystripe)

Έχουμε \(N\) σοκολατάκια, συσκευασμένα και τοποθετημένα στη σειρά το ένα δίπλα στο άλλο σε μία ταινία. Κάποια από αυτά έχουν πικρή σοκολάτα (τα συμβολίζουμε με “B” — bitter) και κάποια έχουν γλυκιά σοκολάτα (τα συμβολίζουμε με “S” — sweet). Για παράδειγμα, η συμβολοσειρά “BSBSSB” παριστάνει μία ταινία αποτελούμενη από 6 σοκολατάκια, στην οποία το πρώτο είναι πικρό, το δεύτερο γλυκό, κ.ο.κ.

Ο αδερφός μας, που είναι δύο χρονών, προτιμάει φυσικά τη γλυκιά σοκολάτα. Δεν γκρινιάζει αν φάει και κανένα πικρό σοκολατάκι. Αν όμως οποιαδήποτε χρονική στιγμή έχει φάει περισσότερα πικρά σοκολατάκια και λιγότερα γλυκά, τότε βάζει τα κλάμματα και εμείς φυσικά δε θέλουμε να τον στενοχωρήσουμε.

Θέλουμε να δώσουμε στον αδερφό μας ένα συνεχόμενο τμήμα της αρχικής ταινίας, πιθανώς κόβοντας ένα κομμάτι από την αρχή ή/και ένα κομμάτι από το τέλος. Ο αδερφός μας θα αρχίσει να τρώει τα σοκολατάκια ένα-ένα, με τη σειρά μέχρι να τελειώσουν, δεν ξέρουμε όμως από ποιο άκρο του τμήματος θα αρχίσει.

Βρείτε το μήκος του μεγαλύτερου τμήματος της αρχικής ταινίας που μπορούμε να δώσουμε στον αδερφό μας και να είμαστε σίγουροι ότι δε θα βάλει τα κλάμματα.

Αρχεία Εισόδου (candystripe.in):

Η πρώτη γραμμή της εισόδου θα περιέχει έναν θετικό ακέραιο αριθμό \(T\): το πλήθος των αρχικών ταινιών για τις οποίες πρέπει να βρείτε τη λύση. Κάθε μία από τις επόμενες \(T\) γραμμές θα αντιστοιχεί σε μία αρχική ταινία και θα περιέχει μία συμβολοσειρά αποτελούμενη από τους χαρακτήρες “B” και “S”.

Αρχεία Εξόδου (candystripe.out):

Η έξοδος πρέπει να περιέχει \(T\) γραμμές, κάθε μία από τις οποίες θα περιέχει ακριβώς έναν ακέραιο αριθμό: την απάντηση στο παραπάνω πρόβλημα για την αντίστοιχη αρχική ταινία.

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

candystripe.in	candystripe.out
5 BSBSSB SSBBSS SBSBSBBSSS SSSBBSBSBSBBB ΒΒΒΒ	4 6 5 5 0

Εξήγηση παραδείγματος: Για την πρώτη ταινία, το μεγαλύτερο τμήμα που μπορούμε να δώσουμε στον αδερφό μας είναι το “SBSS”, δηλαδή αυτό που προκύπτει αν κόψουμε τα δύο ακριανά πικρά σοκολατάκια. Για τη δεύτερη, μπορούμε να τη δώσουμε ολόκληρη στον αδερφό μας. Για την τρίτη, το μεγαλύτερο τμήμα που μπορούμε να του δώσουμε είναι το πρόθεμα “SBSBS”. Το ίδιο και για την τέταρτη, είναι το τμήμα “SBSBS” που προκύπτει αν κόψουμε τα πέντε πρώτα και τα τρία τελευταία σοκολατάκια. Τέλος, για την τελευταία ταινία, δεν υπάρχει κανένα τμήμα της που να μπορούμε να δώσουμε στον αδερφό μας και να είναι χαρούμενος αφού δεν υπάρχουν γλυκά σοκολατάκια.

Περιορισμοί:

\(1 \leq T \leq 10\).
Το μήκος κάθε ταινίας θα είναι \(1 \leq N \leq 1.000.000\).
Το συνολικό μήκος όλων των ταινιών σε κάθε αρχείο ελέγχου δε θα υπερβαίνει το \(2.000.000\).
Όριο χρόνου εκτέλεσης: \(1\) sec.
Όριο μνήμης: \(64\) MB.

Subtasks: