题目背景

那件事…… 绝对不能忘记！

题目描述

你在电脑内记录了一条绝对不能忘记的事。但是，因为 1064 病毒的入侵，它被电脑忘记了。更可怕的是，1064 病毒似乎拥有某种跨物种传播的能力，导致你也忘记了这件事。

万幸，在 1064 病毒让你和你的电脑忘记这件事之前，你及时将这件事的记录复制了 $n$ 份。但是，由于你和你的电脑在执行这件艰巨的任务的过程中受到 1064 病毒的影响忘记了很多可以忘记的事，所以你进行的操作有点奇怪。

• 首先，这件事的记录是一个长度未知（因为你已经忘记了它的长度）的字符串，称作 记录串。对于一份复制，你将记录串切成了三段非空的字符串 片段。不同复制的场合，切割的方案不一定相同。你暂且将这三份 片段 依次称作 前面，中间 和 后面。
• 因为电脑忘记了很多可以忘记的事，所以某些复制中的某些片段可能被忘记了。具体而言，前面有可能被替换为 QIANMIANWANGLE，中间有可能被替换为 ZHONGJIANWANGLE，后面有可能被替换为 HOUMIANWANGLE；在发生替换的场合，表示电脑 完全忘记 了这一段片段；否则，表示电脑 完全记得 该片段。
• 你终于想起了一件绝不能忘记的事：那就是那绝不能忘记的记录串中，恰出现了一次 NFLSPC#6QIDONG 作为连续子串。除此之外，记录串中的所有其它字符都是 小写英文字符。并且，因为你和你的电脑始终记得这件事有多么重要，所以你在划分的时候，无意中让某一个片段恰好为 NFLSPC#6QIDONG；你的电脑也在每一份记录中忠实地记得这一段片段。
• 于是，你的电脑最终还记得的东西，就是：$n$ 份复制，每份复制由三段非空字符串构成，依次表示这份复制的三份片段；其中恰有一段为 NFLSPC#6QIDONG，另外两段要么是一串仅由小写英文字母构成的非空串，要么是对应的前面/中间/后面忘了。
• 邪恶的 1064 病毒不肯罢休，它篡改了你电脑中的信息，使得你的 $n$ 份复制不一定是自洽的。

你确信 1064 病毒没有能力篡改过多的信息，并且它绝对敌不过你和你的电脑对彼此牢牢记住的 NFLSPC#6QIDONG 的信念。因此，你的复制仍然满足上文中所述的性质（恰有一段是 NFLSPC#6QIDONG，另外两段要么忘了要么是小写字母非空串）。

你的目标是，寻找到初始的那绝不能忘记的记录串。这个记录串需要满足的条件是，恰出现一次 NFLSPC#6QIDONG，其余字符均是小写英文字符，且其匹配尽量多的复制串。

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

你希望求出该记录串能匹配的最多复制串数目。至于记录串本身，你更希望将它深深地埋藏于心底，因此你不需要求出它。

那忘记的事只会使你的心灵更加轻盈 / 那未曾忘记的事则会让你的心灵更加坚硬 /

输入格式

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

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

接下来 $n$ 行，每行三个非空字符串，其中第一段要么是非空小写字符串，要么是 Q（表示 QIANMIANWANGLE），要么是 N（表示 NFLSPC#6QIDONG），不存在其它可能；第二段则是非空小写字符串、Z（表示 ZHONGJIANWANGLE）、N 三者之一；最后一段是非空小写字符串、H（表示 HOUMIANWANGLE）、N 三者之一。保证三段中恰有一段为 N。

输出格式

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

3
N Z H
Q N H
Q Z N

1

提示

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

• 子任务 1（$20$ 分）：保证复制中除了 NFLSPC#6QIDONG 恰出现一次以外，其它部分全部忘记。也即，输入的复制串仅可能为 N Z H，Q N H，Q Z N 三者之一。
• 子任务 2（$30$ 分）：保证所有复制串的 “后面” 段都是 NFLSPC#6QIDONG。也即，输入的复制串必然形如 * * N，其中 * 指代任意符合格式的输入。
• 子任务 3（$50$ 分）：无特殊限制。

Source：NFLSPC #6 J by Troverld