Zuma Game

This is a simplified version of the popular Zuma game. In this game, a row of colored beads is given. In each move, you may choose a bead of any color and insert it at any position in the row. When you insert a bead, if it joins with consecutive beads of the same color so that the group (including the inserted bead) has at least 3 beads, that whole group is immediately eliminated. This elimination may cause two beads (or groups) of the same color to become adjacent; if the newly‐formed contiguous group has 3 or more beads, it will also be eliminated automatically. Note that a naturally occurring group of 3 or more (i.e. one that is not extended as a result of an insertion) will not disappear immediately. Your task is to find the minimum number of beads you must shoot (i.e. insert) so that the entire row is eliminated.

Elimination Process Details:

• When you insert a bead, check the contiguous group of beads of the same color that includes the inserted bead. If the total count is at least 3, eliminate that group.
• After elimination, if the beads on the left and right of the removed segment are of the same color and their merged contiguous length is at least 3, they too are eliminated. This chain reaction continues until no more eliminations occur.
• Only groups that are directly affected by an insertion (or subsequently by a chain reaction) will be eliminated.

Input and Task:

You are given a single string representing the row of beads. Each character represents the color of a bead. You may assume that the length of the string is at most 100. Compute the minimum number of beads you must insert so that the board is cleared.

Note: If the row is initially empty, no moves are needed.

inputFormat

The input consists of a single line containing a nonempty string, which represents the row of beads. Each character is an uppercase or lowercase letter representing a bead color.

outputFormat

Output a single integer, the minimum number of inserted beads required to eliminate all the beads.

sample

WRRBBW

3