A deck of cards contains 52 playing cards. The front (or face) of each card carries markings that distinguish it from the other cards in the deck and determines its use under the rules of the game being played. The back of each card is identical for all cards in any particular deck, and usually of a single colour or formalized design.

Consider a sequence of cards that is in front of you on the table, where some of the cards are face down and some are face up.

Now, randomly draw out a group of one or more contiguous cards in which the first and last card are both face down (in a group of one card, the first and last card are the same). Then turn over all cards in this group (including the outermost cards that are face down), while maintainig the original position of each card in the sequence. If you repeat this procedure, you will eventually end up with a sequence where all cards are face up, so that no more groups of contiguous cards can be turned, no matter how you make your choices for the groups of contiguous cards that are turned as a unit.

Assignment

In this assignment, we leave you no choice about the groups of contiguous cards that need to be turned. Instead, we ask you in each turn to draw the sequence between the two outermost cards that are face down. If you stick to this choice, it takes three turns to convert the sequence of cards given above into a sequence of cards that are all face up. This is illustrated in the figure below, where we have indicates the two outermost cards of the sequence that needs to be turned with a yellow glow.

We represent cards that are face up using the letter F, and cards that are face down (back up) using the letter B. This way, we can represent a sequence of cards using a string that only contains the letters F and B. The sequence of cards that has been used in the introduction is then represented by the string FBFFFBFFBF. You are asked to:

• Write a function swap that takes a sequence of cards. The function must return a string that represents the sequence of cards that is obtained if all cards in the given sequence of cards are turned over.

• Write a function next that takes a sequence of cards. The function must return a string that represents the sequence of cards that is obtained if all cards between the two outermost cards that are face down in the given sequence of cards are turned over (including the two outermost cards that are face down). With the outermost cards we intend to say the leftmost and the rightmost cards that are face down. In case the given sequence of cards contains no cards that are face down, the given sequence of cards must be returned by the function.

• Write a function turns that takes a sequence of cards. The function must return the number of turns it takes to obtain a sequence of cards that are all face up, if we start with the given sequence of cards and repeatedly turn over all cards in between the two outermost cards that are face down (including the two outermost cards that are face down).

Example

>>> swap('FBFFFBFFBF')
'BFBBBFBBFB'
>>> swap('BFFBFBFFFBFBBBFBBBBFF')
'FBBFBFBBBFBFFFBFFFFBB'
>>> swap('FFBFBFBFBFBFBFBBFBFBFBFBBFBFBBFBF')
'BBFBFBFBFBFBFBFFBFBFBFBFFBFBFFBFB'

>>> next('FBFFFBFFBF')
'FFBBBFBBFF'
>>> next('BFFBFBFFFBFBBBFBBBBFF')
'FBBFBFBBBFBFFFBFFFFFF'
>>> next('FFBFBFBFBFBFBFBBFBFBFBFBBFBFBBFBF')
'FFFBFBFBFBFBFBFFBFBFBFBFFBFBFFBFF'

>>> turns('FBFFFBFFBF')
3
>>> turns('BFFBFBFFFBFBBBFBBBBFF')
6
>>> turns('FFBFBFBFBFBFBFBBFBFBFBFBBFBFBBFBF')
14