Problem Description

Mirko bought a new microprocessor.

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

After carefully studying the manuals of the two processors, he found the reason.

To work faster, the new processor model imposes certain constraints on the machine code of programs, and these constraints did not exist in the previous model.

The processor’s machine code consists of instructions executed in order. Each instruction uses one byte of memory.

Also, an instruction can have $0$ or more parameters, and each parameter uses one additional byte of memory. In machine code, the parameters come immediately after the instruction.

When written in text form, machine code instructions are uppercase letters, and parameters are lowercase letters. For example:

This program consists of four instructions: the $1$st uses three parameters, the $2$nd uses two parameters, the $3$rd uses none, and the $4$th uses four parameters. The program uses $13$ bytes of memory.

The new processor model fetches memory in blocks of four bytes, so each instruction must start at a memory address divisible by $4$ (the first byte in memory has address $0$).

We can insert NOP (No Operation) instructions into an old program. These instructions do nothing.

Instructions $A$, $B$, $C$, and $D$ are now located at memory positions $0$, $4$, $8$, and $12$, which satisfies the processor’s constraint.

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

Input Format

One line with a string $s$, representing the machine code of a program written for the old processor model.

The program will always start with $1$ instruction, that is, the first character in the machine code is an uppercase letter. If an instruction appears multiple times in the machine code, it will always use the same number of parameters.

Output Format

One line with a positive integer $ans$, representing the minimum number of NOP instructions that need to be inserted.

Abcd 

0

EaEbFabG 

5

AbcbBccCDefgh 

4

Hint

Constraints

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

Notes

• This problem is worth $30$ points in total.
• This problem is translated from COCI2008-2009 CRCI2008-2009 NOP. Translator:
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5