题目背景

好像忘了什么事…… 算了，想必不是什么重要的事吧。

题目描述

你在你的电脑上发现了 $n$ 份文本。冥冥之中，你没来由地感觉这似乎全都是一份记录的复制。

• 首先，原始记录是一个长度未知（甚至可以为空）的字符串，称作 记录串。对于一份复制，其将记录串切成了三段 可以为空 的字符串 片段。每份复制中切割方案不保证相同。你暂且将这三份 片段 依次称作 前面，中间 和 后面。
• 某些复制中的某些片段可能被忘记了。具体而言，前面有可能被替换为 QIANMIANWANGLE，中间有可能被替换为 ZHONGJIANWANGLE，后面有可能被替换为 HOUMIANWANGLE；在发生替换的场合，表示这一段片段被 完全遗忘 了；否则，表示该片段被 完整保存。
• 你有一种预感，记录串中的所有字符都是 小写英文字符。
• $n$ 份复制不一定自洽。

你的目标是，寻找初始的记录串。这个记录串需要满足所有字符均是小写英文字符。你希望其匹配尽量多的复制串。

• 记录串与复制串匹配的要求是，存在记录串的一种划分，使得其中记录串的三段与复制串的三段分别相同，或者复制串中这段划分忘了（此时本段划分中，记录串为任何可以为空的小写英文字符串均合法）。

你希望求出该记录串能匹配的最多复制串数目。至于记录串本身，你感觉它并不是很重要，所以你不需要求出它。

/ 我，毋畏遗忘 /

输入格式

为了避免输入过大，输入进行了一定程度的压缩。请务必认真阅读输入格式。

第一行一个正整数 $n$，表示记录数目。

接下来 $n$ 行，每行三个非空字符串，其中第一段要么是非空小写字符串，要么是 Q（表示 QIANMIANWANGLE），要么是 E 表示这是一段空串（因为空串不可见所以选取 E 作为占位符），不存在其它可能；第二段则是非空小写字符串、Z（表示 ZHONGJIANWANGLE）、E 三者之一；最后一段是非空小写字符串、H（表示 HOUMIANWANGLE）、E 三者之一。

输出格式

一行一个整数，表示所有记录串中，能匹配的最多的复制的数目。

3
nflsalgo Z H
Q nflspc H
Q Z qidong

3

提示

样例 1 解释

你希望这个串是 nflsalgonflspcqidong。你确信，不会再有其它串比它更匹配现存的记录了。

数据范围与约定

对于所有数据，保证输入的所有字符串长度之和不超过 $5\times 10 ^ 5$。

• 子任务 1（$30$ 分）：保证所有复制的 “后面” 段都是 H。
• 子任务 2（$70$ 分）：无特殊限制。

Source：NFLSPC #6 K by Troverld