Minimum NOP Insertion for Code Alignment

Mirko recently purchased a new microprocessor. Unfortunately, programs written for the old processor do not run on the new one. After studying both processor manuals, he discovered the reason.

The machine code for the processor is a sequence of instructions stored in consecutive memory bytes. Each instruction occupies 1 byte and may be followed by zero or more parameters, each occupying 1 extra byte. In text format, an instruction is denoted by an uppercase letter, while its parameters are denoted by lowercase letters. For example, consider a program containing four instructions: the first uses three parameters, the second uses two, the third uses none, and the fourth uses four parameters. Hence, the program occupies 13 bytes in memory.

The new processor fetches memory in blocks of 4 bytes. Therefore, every instruction must start at a memory address that is a multiple of 4 (the first memory byte has address 0). To meet this constraint, we can insert a NOP (No Operation) instruction into the old program. The NOP instruction occupies 1 byte and does nothing.

Your task is to compute the minimum number of NOP instructions that need to be inserted into the program so that every instruction (i.e. every uppercase letter) begins at a memory address divisible by 4.

Formally, assume you are given a string s representing the program, where uppercase letters (A-Z) denote instructions and lowercase letters (a-z) denote parameters. Initially, the memory address is 0. Process the characters in order. For each uppercase letter, if the current memory address pos is not divisible by 4, you must insert enough NOP instructions so that the next available address is a multiple of 4, and then place the instruction. For lowercase letters, simply place them in memory. Determine the total number of inserted NOP instructions.

The alignment condition for an instruction at memory address \( pos \) is given by:

\[ pos \equiv 0 \pmod{4}. \]

inputFormat

The input consists of a single line containing a non-empty string representing the program. The string contains only letters. Uppercase letters represent instructions and lowercase letters represent parameters.

outputFormat

Output a single integer: the minimum number of NOP instructions that must be inserted into the program so that every instruction starts at a memory address divisible by 4.

sample

AaaaBbbCDdddd

4