Cknight gets a string  of length . The string  consists of only character "a" and character "b".

Cknight wants to make string  chaotic. That is to say, string  does not contain string "ab" as its substring.

Cknight can use several operations to achieve that.

In each operation, he can choose a position in and replace the corresponding letter with character "a" or character "b".

He wants to know the minimal number of operations required.