Destroying the Friend

You are given a string S consisting only of lowercase English letters. You are allowed to perform the following operation any number of times:

Choose any substring of S of length 4 and replace it with "love".

Your task is to determine the minimum number of operations needed so that S no longer contains the substring friend.

Definition: A substring is a contiguous sequence of characters from a string. For example, the string aabbcc has substrings like aab or aabb, but not abc because the letters in abc are not consecutive in aabbcc.

Note: The replacement operation does not change the length of the string. Observe that an occurrence of friend in the string can be destroyed by performing an operation on any 4-length substring that lies completely within that occurrence. In other words, if an occurrence of friend starts at index i, then performing an operation on the substring starting at any index j (where i ≤ j ≤ i+2) will remove this occurrence.

Your task is to choose a set of operations (each defined by its starting index) so that every occurrence of friend is "hit" by at least one operation, and the total number of operations is minimized.

Hint: This can be solved as an interval covering problem. For every occurrence of friend at index i, consider the interval [i, i+2]. Then, choose the minimum number of points (starting indices of operations) such that each interval contains at least one point.

inputFormat

The input consists of a single line containing the string S (1 ≤ |S| ≤ 10⁵), where |S| is the length of the string and S contains only lowercase English letters.

outputFormat

Output a single integer: the minimum number of operations needed so that S no longer contains the substring friend.

sample

friend

1