Minimum Reductions in BCKI Combinatory Logic

In combinatory logic, every computable function is expressed as a composition of a few basic combinators. In this problem we study a restricted variant of the BCKW basis, namely BCKI.

A combinator expression in the BCKI basis is defined by the following grammar:

⟨Expression⟩ ::= ⟨Expression⟩ ⟨Term⟩ | ⟨Term⟩
⟨Term⟩       ::= '(' ⟨Expression⟩ ')' | 'B' | 'C' | 'K' | 'I'

An expression represents a tree of left‐associative function applications. For example, the expression BIC is interpreted as ((B I) C) and not as (B (IC)).

The evaluation (reduction) is performed by repeatedly finding a redex – a sub‐expression that matches one of the patterns in the table below – and replacing it with its reduction result:

The redex may appear anywhere in the expression, and after each replacement the process is repeated until no redexes remain – the expression is then in normal form. It can be shown that while the final normal form is independent of the order of reductions, the number of steps may vary.

Your task is to compute the minimal number of reduction steps required to reduce a given combinator expression to its normal form.

inputFormat

The input consists of a single line containing a valid combinator expression. The expression will only contain the characters 'B', 'C', 'K', 'I' and parentheses '(', ')'.

outputFormat

Output a single integer – the minimal number of reduction steps needed to reduce the expression to its normal form.

sample

I

0