Ritisha has a pet cockatiel called Kiki, and she has made a successful social media business by posting Kiki in a variety of absurd situations, such as scrolling reels at night time, and dancing and singing. However, some followers keep leaving comments on the posts featuring Kiki calling her a chicken, which enrages Ritisha! Clearly Kiki is very different to a chicken, she is so very differently coloured and shaped! Ritisha wants to make sure no one reads these comments and is misled, so she vows to comb through them and remove all that are chicken-like.

A comment is a string, and it is defined to be 'chicken-like' if it contains the subsequence "chicken" (i.e., you can delete zero or more characters in the string to obtain "chicken" without changing the order).

Ritisha insists on removing characters from the string to ensure that the resulting comment is not chicken-like, so that no misinformation is spread.

• Ritisha may remove any number of characters (possibly zero)
• The relative order of all remaining characters must remain the same
• Ritisha wants to remove the minimum number of characters to make the string not chicken-like

Your task is to compute this minimum number for a given comment string.

Input

The first line contains a single string ~s~ ~(1 \leq |s| \leq 2\times 10^5)~. This string represents the comment to modify, and it only contains lowercase English characters.

Output

Output a single integer: the minimum number of characters that must be removed so that ~s~ is not chicken-like as defined above.

Example

Input 1

chicken

Output 1

1

Removing any character breaks the only "chicken" subsequence.

Input 2

chichickenken

Output 2

2

There are multiple overlapping "chicken" subsequences. Two removals are required. There are many such solutions, but one is "hihickenken", or "chichikeke", etc.

Input 3

joinaucpl

Output 3

0

While incredibly true, the string is already not chicken-like.

Input 4

chickechickechickechickechicken

Output 4

1

Clearly removing the single n at the end breaks all the subsequences.