Problem Description

In the country of E869120, following the IOI country, a new railway has been laid.

The train running on the railway of E869120 consists of several connected carriages, and there are two types of carriages: $ I $ and $ O $.

However, they must be connected according to the following rules:

• Each carriage can only be connected to a carriage of a different type.
• Due to the need to provide a driver's cab, both ends of the train must be of type $ I $.

A train is represented by a string concatenating the characters representing the types of carriages, and the length of the train is the length of this string.

For example, $ IOIOI $ and $ IOIOIOIOIOIOIOIOI $ meet the conditions.

Now, in the depot, there is a state where carriages represented by the string $ S $ are connected.

The carriages to be formed must be a subsequence of $ S $.

At that time, what is the maximum number of carriages that can be formed into a train?

• If you choose the 1st, 2nd, 4th, 6th, 7th, 8th, 9th, 11th, and 12th carriages, you can make the train " $ IOIOIOIOI $ ".

• If you choose the 1st, 2nd, 3rd, 4th, 5th, 7th, 8th, 9th, and 10th carriages, you can make the train " $ IOIOIOIOI $ ".

Input Format

The input is given from the standard input in the following format.

$ S $

• The first line gives the string $ S $ representing the state of the depot.

Output Format

The output should follow the standard output in the following format.

• Output the number of carriages that can be formed in one line.
• However, if no train can be formed, output $ 0 $.

Sample Input and Output

Sample Input #1

IOOIIOIOIIOI

Sample Output #1

9

Sample Input #2

IOIOIIOIOI

Sample Output #2

9

Sample Input #3

None

Sample Output #3

3

Notes/Hints

Constraints

• $ 1 ≦ | S | ≦ 50,000 $

Subtasks

Subtask $ 1 $ \[ $ 25 $ points \]

• Satisfies $ 1 ≦ | S | ≦ 100 $.

Subtask $ 2 $ \[ $ 75 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分