408768: GYM103306 C Cut the Deck

Alice and Bob are playing a new game with cards, the game is played with a deck which contains $$$N$$$ cards, each card has a color blue or red, and half of the cards in the deck are blue, half are red. At the beginning of the game Alice will shuffle the deck, and will ask Bob to "cut the deck", which means to take a stack of cards off the top from the deck and place it on the bottom. For example, if a deck with $$$6$$$ cards has the following configuration after shuffling: 'BRRRBB' and Bob cuts the deck at card $$$2$$$, then the resulting deck will be 'RRBBBR'. Once the deck is cut by Bob, the game begins, Alice will start from the top of the deck, turning one card at a time, if in some point there are more red cards showing than blue cards, then, Alice wins the game, if Alice gets to turn all the cards from the deck, then Bob wins.

Bob insists this is unfair as he has not been able to win any of the games against Alice, he believes the secret for him to win is to properly select the card at which he has to cut the deck, so he will practice his technique shuffling a deck of cards and then selecting the card where to cut. Can you help Bob to given a deck configuration determine where he has to cut the deck in order to win the game?

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$), the number of test cases. Each of the next $$$T$$$ lines contains a string $$$S$$$ representing the deck Bob has to cut, if the character at position $$$i$$$ in the string is a 'B', it means the card at position $$$i$$$ has blue color, if the character is 'R', the card has a red color. The length $$$N$$$ ($$$1 \leq N \leq 10^6$$$) of the string will always be even, and it is guaranteed it has the same amount of 'R' and 'B'.

For each test in the input print a line containing the number of cards Bob has to take from the top of the deck when cutting the deck so he can win the game, if more than one solution exists, print the one with the fewest number of cards. In case this is not possible print "-1" for that case.

3
BRBR
RBRB
BBRRRB

0
1
5