Magnus

Interview

Time limit1sMemory limit512 MB

Summary

Delete any letters from a length-N uppercase word so the kept letters contain as many disjoint subsequences "HONI" as possible, and print that maximum.

Level: Medium5 of 10
Topics: Greedy, String, Two pointers
Solved: No attempts yet

Problem

Magnus lost a game of chess to Kile, so he found comfort in competitive programming. Very soon, he heard of the iconic COCI competition and decided to try his luck there.

He wrote a mail to Kile: "Dear Kile, please, prepare me for COCI. Magnus".

Kile replied: "You want to participate in COCI? All right, here's your warm-up task. A series of four consecutive letters of some word that make up the subword "HONI" (Croatian acronym for COCI) is called the HONI-block. I will send you the word of length N and you will throw out as many letters as you want (it might be none as well) so that in the end there are as many HONI-blocks as possible in the word. Kile".

Magnus was very worried and asked you, COCI competitive scene, for help. Help him determine the maximum number of HONI-blocks he can get in the final word.

Input

The first line contains a word of length N (1 ≤ N ≤ 100 000), consisting of uppercase letters of the English alphabet.

Output

In the first and only line print out the required number of HONI-blocks.

Examples3

Example 1
Input
```
MAGNUS
```
Expected output
```
0
```
Example 2
Input
```
HHHHOOOONNNNIIII
```
Expected output
```
1
```
Example 3
Input
```
PROHODNIHODNIK
```
Expected output
```
2
```