Problem Description

Mirko has purchased a new microprocessor.

Unfortunately, he found that many programs written for the old processor do not run on the new processor.

After delving into the manuals for both processors, he discovered the reason.

To work faster, the new processor imposes certain constraints on the machine code of programs, constraints that were not present in the previous models.

The machine code of the processor consists of instructions executed sequentially. Each instruction uses one byte of memory.

Similarly, instructions can have zero or more parameters, each of which uses an additional memory byte. In the machine code, parameters follow the instruction.

When set in text format, machine code instructions are uppercase letters, while parameters are lowercase letters. For example:

This program consists of four instructions: the first one uses three parameters, the second one uses two parameters, the third one uses none, and the fourth one uses four parameters. This program uses 13 bytes of memory.

The new processor model fetches memory in four-byte blocks, so each instruction must start at a memory address that is a multiple of four (the first byte in memory is address 0).

We can insert NOP (No Operation) instructions into the old program, which do nothing.

Instructions $A$, $B$, $C$, and $D$ are now at memory locations 0, 4, 8, and 12, respectively, which satisfies the processor's constraints.

Please write a program to find the minimum number of NOP instructions needed to be inserted.

Input Format

A single line containing a string $s$, representing the machine code of the program written for the old processor model.

The program will always start with one instruction, i.e., the first uppercase letter in the machine code. If an instruction appears multiple times in the machine code, it will always use the same number of parameters.

Output Format

A single line containing a positive integer $ans$, representing the minimum number of NOP instructions needed to be inserted.

Sample Input and Output

Sample Input #1

Abcd

Sample Output #1

0

Sample Input #2

EaEbFabG

Sample Output #2

5

Sample Input #3

AbcbBccCDefgh

Sample Output #3

4

Notes/Hints

Data Size and Constraints

Let $|s|$ be the number of characters in string $s$. For $100\%$ of the data, $1 \le |s| \le 200$.

Notes

• This problem is worth 30 points.
• This problem is translated from COCI2008-2009 CRCI2008-2009 NOP, translated by @tearing.

见题面 Input 部分

见题面 Output 部分