Pseudo-Banana Strings

A pseudo-banana is defined by the following rules:

• $BANANA$ is a pseudo-banana.
• For a pseudo-banana $X$, $BX$ with $B$ prepended is also a pseudo-banana.
• For a pseudo-banana $X$, $XNA$ with $NA$ appended is also a pseudo-banana.

Hence every pseudo-banana has the form $B^{a}ANANA(NA)^{t}$ with integers $a >= 1$ and $t >= 0$, and its length is $a + 5 + 2t$.

A pseudo-banana string is a concatenation of one or more pseudo-bananas. Given a string over $B$, $A$ and $N$, determine the minimum number of character replacements needed to turn it into a pseudo-banana string.

A string $S$ of length $M$ is given on one line. $S$ consists only of the characters $B$, $A$ and $N$. $M$ satisfies $6 <= M <= 100000$.

Print on one line the minimum number of character replacements needed to turn the given string into a pseudo-banana string. Every input with length at least 6 admits such a string, so an answer always exists.

One pseudo-banana consists of one or more $B$ characters, followed by $ANANA$, followed by zero or more repetitions of $NA$. A full string is a repetition of such blocks, where after a block boundary either the $B$ starting the next block or the $N$ continuing the tail may appear.

This structure can be expressed as a deterministic finite automaton with 8 states. Matching the input against it reduces to dynamic programming that keeps, for each position, the cheapest cost of reaching every state.