Chef likes playing with strings. The most interesting game are named "CHEF in string". The move of the game consists of the following: Chef takes a subsequence of string's letters that form the word "CHEF" and then he removes that symbols. The goal of the game is to make the maximal number of moves. Please, help Chef and tell him the maximal possible number of moves that he is able to make for the given string S.

Input
 The first line of each test case contains a given string. This string consists of uppercase letters from the set {"C", "H", "E", "F"}. 

Output
Output a single line containing the maximal possible number of moves.

Constraints

1  ≤ |S| ≤ 100000


Example
Input:
CHEFCHEFFFF

Output:
2

Input:
CHHHEEEFFCC

Output:
1


Scoring
Subtask 1 (25 points): |S| ≤ 2000 
Subtask 2 (75 points):  See the constraints.
chef = raw_input()

def find_index(chef, index):
    c1,h1,e1,f1 = index
    c = chef.find('C', c1+1)
    if c<0:
        return None
    h = chef.find('H', max(c+1, h1+1))
    if h<0:
        return None
    e = chef.find('E', max(h+1, e1+1))
    if e<0:
        return None
    f = chef.find('F', max(e+1, f1+1))
    if f<0:
        return None
    return [c,h,e,f]

count = 0
index = find_index(chef, [-1,-1,-1,-1])
while index:
    index = find_index(chef, index)
    count += 1

print count