NOP - Nop

no tags 

Mirko purchased a new microprocessor. Unfortunately, he soon learned that many of his programs that he wrote for his old processor didn't work on the new processor.

Deep inside the technical documentation for both processors, he found an explanation. In order to work faster, the new processor imposes certain constraints on the machine code of programs, constraints that never existed on the previous model.

The machine code of a processor consists of instructions that are executed sequentially. Each instruction uses a byte of memory. Also, instructions can have zero or more parameters, each of which uses an additional byte of memory. In machine code, parameters immediately follow an instruction.

When formatted as text, machine code instructions are uppercase letters, while parameters are lowercase letters. For example:

A b c b B c c C D e f g h

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

The new processor model fetches memory in four-byte chunks so each instruction must start at a memory address that is divisible by four (the first byte in memory is address 0). To achieve that, we can insert NOP (no operation) instructions into the old program, instructions that do nothing and are not limited to memory locations divisible by four. The above program, adapted to run on the new processor, can look like this:

A b c b B c c NOP C NOP NOP NOP D e f g h

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

Write a program that determines the smallest number of NOP instructions that need to be inserted for the given program to work on the new processor model.

Input

The input contains the machine code of the program written for the old processor model. The program will consist of at most 200 English letters.

The program will always start in an instruction i.e. the first letter in the machine code will be uppercase. If an instruction appears more than once in the machine code, it will always take the same number of parameters.

Output

Output the smallest number of NOP instructions needed to adapt the program for the new processor.

Example

Input
Abcd

Output
0


Input
EaEbFabG

Output
5


Input
AbcbBccCDefgh

Output
4

Score is your source code length. Have fun!


hide comments
Dilpreet: 2016-06-28 06:44:37

Be careful the input contains non English letters. costed me 1 WA

dwij28: 2016-01-24 19:25:52

Why is it not mentioned that the input has non english alphabet letters ? Cost me one WA .. It feels horrible to get WA on problems like these, moreover when its not even my fault.. :/

jagdish chaudhary: 2015-01-26 08:57:38

any can explain in2nd test case why it is 5 i think it should be 7

V Y: 2014-11-28 19:30:05

See there are really poor test cases.
But you have tried it so don't leave it half-way.
AabcdB: 3
AaBcdefgC: 4

Last edit: 2014-11-28 19:30:29
Ashwini: 2013-10-31 22:38:41

Why wrong answer please help.
Even considered the case of parameters greater than 3

Mostafa 36a2: 2013-07-27 04:13:13

47 bytes in AWK :)

Mostafa 36a2: 2013-07-26 04:55:45

@Mitch : thank you ,i've read the comments of course, the line is terminated by \r not \n I knew this,
but NZECs confusing me
submittions
9722005,9722007,9722009
Are EXACTLY the same ,with different results !!! AC,NZEC,NZEC
with assert on char==ASCII(20) O_o

I agree with you about 'changing old problems' issue ,but it still annoying :p can you delete this comment :p

Last edit: 2013-07-26 11:10:49
Mitch Schwartz: 2013-07-26 02:53:54

@Mostafa: Did you read the previous comments? Are you sure the "random characters" aren't simply '\r' (ASCII 13)? I agree formatting issues are annoying. For newer challenge problems it makes sense to ask for data to be cleaned up, for older problems I think it's best to leave them as they are, as it may change the nature of the problem in a non-trivial way -- the best solutions (in a given language, or overall) may be specially adapted to the formatting. Note that I refer here only to formatting issues; for actual incorrect data/judge like DDATE and possibly DELIVERY, corrective action by the problem setter would be most welcome.

Mostafa 36a2: 2013-07-25 18:58:53

The input is really annoying!
can Some One fix it , the line contains random chars instead of lower case alphabet !

(Edit) :) Why no body tried AWK here ? ;)

Last edit: 2013-07-26 02:53:16
abpdora: 2012-01-19 09:38:59

my problem id is XXXXXXX can you tell me what could i be missing

it works now witha tweak . i guess the i/p has charaters apart from [A-Za-z]

Last edit: 2012-01-19 09:51:05

Added by:Race with time
Date:2009-02-17
Time limit:0.910s
Source limit:360B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COCI 2008/2009 - Croatian Regional