The longest sequence P69932

You are given several natural numbers. Put some of the numbers side by side according to these rules:

• the resulting sequence must be increasing;

• there cannot be two even numbers together nor two odd numbers together.

Write a program such that, for every given line, prints the length of the longest sequence that can be produced according to the rules above using the numbers on that line.

Input

Input consists of several lines. Each line contains a sequence of natural numbers.

Output

For each line of the input, print a line with the length of the longest sequence that can be made according to the rules given above.