To conclude this year's edition of the Algorithm Tamers, the Krzysieks responsible for the smooth running of the competition (KC, KD, KO, KS) decided to perform a joyful Gordian dance. The Gordian dance is a traditional Bajtok dance performed by two pairs of dancers. Initially, the dancers stand at the vertices of a square $ABCD$, in two pairs: $A$ - $B$ and $C$ - $D$. Each pair stretches a string between them. Thus, at the beginning, both strings are stretched horizontally and parallel to each other.

The dance consists of a sequence of moves, each of which can be one of the following types:

• (S) The dancers standing at points $B$ and $C$ swap places (without letting go of their strings) in such a way that the dancer standing at point $B$ raises their hand with the string and, while moving to point $C$, passes the dancer moving from point $C$ to $B$ in front of them, under their hand.
• (R) All dancers perform a 90-degree turn to the right without letting go of the strings, meaning the dancer who stood at point $A$ goes to point $B$, the one who stood at point $B$ goes to point $C$, the one who stood at point $C$ goes to point $D$, and the one who stood at point $D$ goes to point $A$.

During the dance, the strings become tangled, but by the end of the dance, they should be untangled and again stretched horizontally and parallel to each other. The dancers do not have to be standing in the same places they occupied at the beginning. This dance requires great skill from the dancers, as the strings can become very tangled during the dance, and the sequence of moves that would lead to them being untangled and stretched horizontally and parallel to each other can be difficult to guess.

The Krzysieks are beginner dancers. Your task is to write a program that will help them finish the dance they have started. Based on the sequence of moves already performed, your program should determine the minimum number of moves required to finish the dance.

For example, after performing the sequence of moves SS, we obtain the following configuration:

The shortest sequence of moves that allows the dance to be finished has a length of 5 and is RSRSS.

Write a program that:

• reads from standard input the description of the sequence of moves performed in the dance,
• determines the minimum number of moves needed to untangle the strings and stretch them horizontally and parallel to each other (after performing these moves, the dancers do not have to be in their initial positions),
• prints the result to standard output.

Input

The first line of standard input contains a single positive integer $n$ equal to the number of moves performed, $1 \le n \le 1000000$. The second line contains a single word of length $n$ consisting of the letters S and/or R. The consecutive letters of this word represent the moves performed in the dance in order.

Output

Your program should print to standard output, in the first and only line, a single integer - the minimum number of moves (S and/or $R$) necessary to untangle the strings and stretch them horizontally and parallel to each other.

Examples

Input 1

2
SS

Output 1

5