Problem Background

What is friendship?
The wind doesn't know.
But when friendship leads to suspicion in love
The wind chooses to end friendship because of friendship

Problem Description

String $S$ is a sequence consisting only of lowercase English letters. Now, you can perform the following operation on string $S$ any number of times:

• Select a substring of $S$ that is exactly 4 characters long and replace it with love.

How many times do you need to perform this operation at a minimum for string $S$ to no longer contain the substring friend.

Definition: A substring is a continuous sequence of characters within a string. For example, the string aabbcc has substrings aab, aabb, but abc is not a substring of aabbcc because it is not continuous.

Input Format

Input consists of a single line containing the string $S$.

Output Format

Output a single integer, representing the minimum number of operations required.

Sample Input and Output

Sample Input #1

friend

Sample Output #1

1

Sample Input #2

friendzdxfriend

Sample Output #2

2

Notes

For $20\%$ of the test cases, $1 \le |S| \le 6$;
For $100\%$ of the test cases, $1 \le |S| \le 10^6$, and $S$ consists only of lowercase English letters.

见题面 Input 部分

见题面 Output 部分