問題文
アルファベット小文字(a-z)のみで構成された文字列があります。
ここで文字列の部分文字列(substring)に tourist が $x$ 個存在するとき, 観光客が $x$ 人いると定義します。
部分文字列は連続である必要があります。またある部分文字列と別の部分文字列が被っていても別々に数えることとします。
文字列に対し以下の操作を何回か行うことにより, 観光客がちょうど $1$ 人の状態にしたいです。
- 文字列のある $1$ 文字を別の好きなアルファベット小文字 $1$ 文字に置換する。
このとき, 操作の最小回数を求めてください。
入力
S
$1$ 行に, アルファベット小文字(a-z) のみから構成された文字列 $S(7 \le |S| \le 50\ 000)$ が与えられます。
出力
$1$ 行に, 操作の最小回数を出力してください。
入出力例
入力例1
redredtourist
出力例 1
0
もともと $1$ 人の場合は置換する必要がありません。
入力例 2
touristouristgod
出力例 2
1
観光客が $2$ 人います。
例えば $1$ 文字目の t を別の $1$ 文字に置換することにより, 観光客を $1$ 人にできます。
入力例 3
kankokyaku
出力例 3
6
以下の文字列になるように置換します。
kantourist