Going to School

\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 to compute the smallest number of streets she needs to cross on her path to school.


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.


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


Your program will be tested on 5 test cases. For each test case you pass, you get 20 points.

For test cases worth 40 points, the number of letters will be at most $20$.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2