著名的纸牌游戏制造商 Greatest Cards Production Company (GCPC) 刚刚推出了全新的纸牌游戏 Jabberwocky。在这个游戏中，每个人都会分到相同数量的牌——数量可能相当多——每张牌都属于四种花色之一：红桃 (hearts)、方块 (diamonds)、梅花 (clubs) 或黑桃 (spades)。

作为资深的纸牌游戏迷，Alice 和她的朋友们非常兴奋地聚在一起，想要尝试这款最近大家都在谈论的纸牌游戏。由于交通堵塞，Alice 到达聚会时迟到了，她的朋友们正在不耐烦地等她。大家已经分好了所有的牌，除了 Alice 之外，每个人都准备好开始了。Alice 刚拿到她的牌，并坚持要先按花色对它们进行排序。为此，她会反复从手中取出一张牌，并将其插入到其他位置，直到她的牌按花色分组为止。她的朋友们对 Alice 越来越恼火，而她也想尽快排好她的牌。Alice 在开始游戏前最少需要移动多少张牌？

图 J.1：在样例 1 中，Alice 至少需要移动两张牌才能排好她的手牌。

输入格式

输入包含： * 一行包含一个字符串 $s$ ($1 \le |s| \le 10^5$)，表示 Alice 手牌的初始花色顺序。该字符串由字符 h、d、c 和 s（分别代表红桃、方块、梅花和黑桃）组成。

输出格式

输出一个整数，表示 Alice 为按花色排序手牌所需移动的最少牌数。

样例

样例输入 1

hccdhcd

样例输出 1

2

样例输入 2

cchhdshcdshdcsh

样例输出 2

7