Combinator Expression

Problem

Combinatory logic is a computation model that expresses any computable function as a composition of functions from a small fixed basis. This problem uses BCKI, a restricted form of the BCKW basis.

A combinator expression over BCKI is a string produced by the grammar below.

<Expression> ::= <Expression> <Term> | <Term>
<Term>       ::= '(' <Expression> ')' | 'B' | 'C' | 'K' | 'I'

An expression is a tree of applications whose leaves are the combinators $B$ , $C$ , $K$ and $I$ . Application is left associative, so $BIC$ is the same as $(BI)C$ and is not the same as $B(IC)$ .

In the explanations below, lowercase English letters a to z stand for sub-expressions. They never appear in the input. For example, $BIC$ matches the shapes $BxC$ (with $x = I$ ), $x$ (with $x = BIC$ ), $xy$ (with $x = BI$ and $y = C$ ) and $Bxy$ (with $x = I$ and $y = C$ ), but it does not match $Bx$ .

In the expression $pq$ we say that $p$ is applied to $q$ . You can read $p$ as a function and $q$ as its argument. The evaluation is not the usual passing of values through a fixed tree. Each step rewrites the tree, and the result is again a combinator expression.

One step picks a sub-expression that matches one of the patterns in the table, meaning there are sub-expressions $x$ (and possibly $y$ and $z$ ) that make the pattern equal to the chosen sub-expression. The step then replaces that sub-expression with the reduction result.

Pattern	Reduction result	Name
$Bxyz$	$x(yz)$	composition function
$Cxyz$	$(xz)y$	exchange function
$Kxy$	$x$	constant function
$Ix$	$x$	identity function

Steps repeat until no sub-expression matches any pattern. The expression that remains is the normal form of the original one.

Take $CIC(CB)I$ , which reads as $(((CI)C)(CB))I$ . With $x = I$ , $y = C$ and $z = CB$ , the sub-expression $(((CI)C)(CB))$ equals $Cxyz$ , so it becomes $(xz)y = I(CB)C$ and the whole expression becomes $I(CB)CI$ .

Now take $B((CK)I)IC$ . Reducing $B$ with $x = (CK)I$ , $y = I$ and $z = C$ gives $((CK)I)(IC)$ . Reducing the inner $I$ gives $((CK)I)C$ . Reducing $C$ gives $(KC)I$ , and reducing $K$ leaves $C$ .

The normal form does not depend on the order of the steps, but the number of steps does. In $C(K(II)(IC))$ , reducing the inner $IC$ first gives $C(K(II)C)$ , then $II$ gives $C((KI)C)$ , then $K$ gives $CI$ , which is three steps. Reducing $II$ first gives $C((KI)(IC))$ , and then $K$ throws $(IC)$ away and gives $CI$ in two steps.

Write a program that finds the smallest number of reduction steps that take a given combinator expression to its normal form.

Input

The first line contains a combinator expression that follows the grammar above. Its length is at most 30000. The line has no whitespace and no character outside the grammar.

Output

Print one integer, the smallest number of reduction steps needed to bring the given expression to its normal form.