Volodya 喜欢听重金属音乐和(偶尔)阅读。难怪沃洛佳对有关他最喜欢的音乐风格的文本特别感兴趣。
如果一根弦以“heavy”开头并以“metal”结尾,Volodya 称该弦为“强力”。在给定文本中找到所有强大的子字符串(子字符串 Volodya 表示字符串中连续字符的子序列)使我们的英雄特别高兴。最近,他在阅读某篇文章时,感到一股巨大的能量。于是沃洛佳决定数一下这段文字中所有强大的子串,并整天吹嘘它。帮助他完成这项艰巨的任务。如果两个子字符串出现在文本中的不同位置,则认为它们不同。
为简单起见,我们假设 Volodya 的文本可以表示为单个字符串。
输入
输入包含由小写拉丁字母组成的单个非空字符串。该字符串的长度不会超过 106 个字符。
输出
精确打印一个数字——给定字符串的强大子字符串的数量。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
heavymetalisheavymetal
输出 #1
3
输入 #2
heavymetalismetal
输出 #2
2
输入 #3
trueheavymetalissotruewellitisalsosoheavythatyoucanalmostfeeltheweightofmetalonyou
输出 #3
3
注意
在第一个样本中,字符串“heavymetalisheavymetal”包含两次强大的子字符串“heavymetal”,而且整个字符串“heavymetalisheavymetal”当然也很强大。
在第二个示例中,字符串“heavymetalismetal”包含两个强大的子字符串:“heavymetal”和“heavymetalismetal”。