Zadanie Zakręty (A) (zak)

Turns [A]

Memory limit: 128 MB

Byteman decided to go for a ride in his car to the mountains. He took a map with him, however, he is not able to locate himself on the map.

The road on the map is represented by turns, each of which is turn to the right or to the left. For simplicity we can represent the map by -letter string consisting of L and/or P letters.

Assuming that Byteman has the 'th turn in front of him (he might not know, however, that it is the 'th turn), by we represent the number of turns Byteman has to drive through, in order to be sure in which place on the map he is located.

We will explain the meaning of the number using an example. Let's assume that road on the map is represented by a string LLPPLPL (L represents a left turn and P - a right turn, for "prawo" means right in Polish). If Byteman is in front of his second turn, before passing that turn he knows that he could be in front of one of the turns: , , or (as he sees a left turn in front of him). After passing that turn, Byteman sees a turn to the right - P, which means that initially he could not had been in front of the first turn (as the following turn was to the left) as well as the last turn (as it is followed by the end of the road). Therefore, he knows that he is in front of third or sixth turn on the map. After passing that turn, Byteman sees a turn to the right - P, which means that initially he could not had been in front of the fifth turn. This leads to the observation, that after passing two turns Byteman is in front of the fourth turn, so .