Hide

Problem B
Going to School

Languages en sv
\includegraphics[width=0.8\textwidth ]{skolvag.png}
Figure 1: The dotted line shows Cissi’s optimal path in the first example.

Cissi is walking from her home to school, following a long street going from the west to the east. On her way, she passes a number of street crossings where the crossing street either goes north (N), south (S) or both (B). At every street crossing, there are crosswalks on both the crossing streets and the main street (see the figure above), and she can only cross the street on the crosswalks.

Her home is to the north of the main street, furthermost to the west. The school is to the north of the main street, furthermost to the east. Write a program that helps Cissi compute the smallest number of streets that she must cross on her path to school.

Input

The input contains a single line with at most $1\, 000$ letters, each of which is N, S or B. The letters describe the crossing streets exactly in the order Cissi will pass them on her way to school.

Output

A single line with an integer, the smallest number of streets Cissi needs to cross.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

Group

Points

Constraints

$1$

$40$

There are at most $20$ crossing streets

$2$

$60$

No further constraints.

Sample Input 1 Sample Output 1
SNBNNSB
4
Sample Input 2 Sample Output 2
SBSNNBSNNSSSNNNB
8