Brickor

Time limit1sMemory limit1024 MB

Summary

Given a short row of black and white pieces, repeatedly remove an adjacent pair, flip both, and append them to either end, to turn all pieces white with the fewest moves.

Level: Medium6 of 10
Topics: BFS, Implementation, Bit manipulation
Solved: No attempts yet

Problem

Karin has invented a solitaire game played with Othello pieces, which are black on one side and white on the other. She lays out a row of pieces, each of which can be black or white. The goal is to get every piece to have its white side facing up.

A "move" is to "pick out" an adjacent pair of pieces from somewhere in the sequence, flip them over (white becomes black, black becomes white), and put them back either at the beginning of the row or at the end of the row, without changing the relative order of the pair.

Write a program that, given the initial row of pieces, prints the minimum number of moves needed to make all pieces white.

Input

The input consists of a string containing only the letters S and V. The string is between 3 and 15 characters long.

Output

Print a single number: the minimum number of moves needed to make all pieces white. For the given test data, it is always possible to reach the goal.

Hint

A possible move sequence in example 2

Examples2

Example 1
Input
```
SVVSVVV
```
Expected output
```
2
```
Example 2
Input
```
VSVSSSVVVV
```
Expected output
```
4
```