Chandelier

The Lamps-O-Matic company assembles very large chandeliers. A chandelier is built from several levels. On the first level, crystal pendants are attached to rings. The assembled rings, together with new pendants, are then attached to the rings of the next level, and so on. In the end a single large ring is left — the finished chandelier, with many smaller rings and pendants hanging from it.

A special assembly robot builds the chandelier. It has an unlimited supply of crystal pendants and empty rings, plus a stack that holds elements during assembly. The stack starts empty, and the robot follows a list of commands.

• Command a: take a new crystal pendant and push it onto the top of the stack.
• Command 1–9: pop that many items from the top of the stack, attach them one after another to a new ring (the item popped first, i.e. the one that was on top, is attached first), then push the newly assembled ring onto the stack.

After the whole program has run, exactly one item is left on the stack — the complete chandelier. A pendant, or any assembled ring no matter how complex, counts as one item on the stack.

For some programs the stack has to hold too many items at once. Determine the smallest possible stack capacity that still lets the robot assemble a chandelier of the same design.

Two chandeliers have the same design if every ring holds the same items in the same order. Because a ring is circular, it does not matter which item ends up on top of the stack when the robot builds that ring — only the cyclic order of the items matters (rotations are allowed, but the order may not be reversed). For example, if the robot runs command 4 while items $\langle i_1, i_2, i_3, i_4 \rangle$ sit on top of the stack (with $i_1$ on top), the very same ring is produced by any of the arrangements $\langle i_2, i_3, i_4, i_1 \rangle$, $\langle i_3, i_4, i_1, i_2 \rangle$, or $\langle i_4, i_1, i_2, i_3 \rangle$.

A single line containing a valid program for the robot. The program consists of at most $10\,000$ characters, where each character is either a or a digit from 1 to 9.

Print a single integer — the minimal stack capacity (the maximum number of items the stack must hold at the same time) needed to assemble a chandelier of the same design.