Background

That thing…… must never be forgotten!

Problem Description

You once stored something on your computer that must never be forgotten. However, due to the invasion of the 1064 virus, it was forgotten by the computer. Even worse, the 1064 virus seems to have some ability to spread across species, causing you to forget it as well.

Fortunately, before the 1064 virus made both you and your computer forget it, you copied the record of this thing into $n$ copies in time. But since you and your computer, while carrying out this difficult task, were affected by the 1064 virus and forgot many things that could be forgotten, your operations became somewhat strange.

• First, the record of this thing is a string of unknown length (because you have forgotten its length), called the record string. For each copy, you cut the record string into three non-empty string segments. In different copies, the cutting scheme may be different. For convenience, call these three segments in order front, middle, and back.
• Because the computer forgot many things that could be forgotten, in some copies, some segments may be forgotten. Specifically, the front may be replaced by QIANMIANWANGLE, the middle may be replaced by ZHONGJIANWANGLE, and the back may be replaced by HOUMIANWANGLE. If a replacement happens, it means the computer completely forgot that segment; otherwise, it means the computer completely remembers that segment.
• You finally recalled one thing that must never be forgotten: in that record string, NFLSPC#6QIDONG appears exactly once as a contiguous substring. Besides that, all other characters in the record string are lowercase English letters. Also, because you and your computer always remembered how important it was, when you partitioned it, you unintentionally made one segment exactly NFLSPC#6QIDONG, and your computer faithfully remembered this segment in every copy.
• Therefore, what your computer finally still remembers is: $n$ copies, each copy consists of three non-empty strings in order, representing its three segments; exactly one of them is NFLSPC#6QIDONG, and the other two are either a non-empty string consisting only of lowercase English letters, or the corresponding front/middle/back was forgotten.
• The evil 1064 virus would not give up. It tampered with the information on your computer, so your $n$ copies may no longer be self-consistent.

You are sure that the 1064 virus is not capable of tampering with too much information, and it can never defeat the belief that you and your computer firmly remember NFLSPC#6QIDONG. Therefore, your copies still satisfy the properties described above (exactly one segment is NFLSPC#6QIDONG, and the other two are either forgotten or non-empty lowercase strings).

Your goal is to find the original record string that must never be forgotten. This record string must satisfy: NFLSPC#6QIDONG appears exactly once, all other characters are lowercase English letters, and it matches as many copy strings as possible.

• The matching requirement between a record string and a copy string is: the record string has a way to partition into three non-empty segments such that the three segments are respectively identical to the three segments of the copy string, or the corresponding segment in the copy string is forgotten (in this case, for this segment, any non-empty English string in the record string is valid).

You want to compute the maximum number of copy strings that a record string can match. As for the record string itself, you would rather bury it deep in your heart, so you do not need to output it.

The forgotten things will only make your soul lighter / The unforgotten things will make your soul harder /

Input Format

To avoid the input being too large, the input is compressed to some extent. Be sure to read the input format carefully.

The first line contains a positive integer $n$, the number of records.

The next $n$ lines each contain three non-empty strings. For the first segment, it is either a non-empty lowercase string, or Q (meaning QIANMIANWANGLE), or N (meaning NFLSPC#6QIDONG); there are no other possibilities. The second segment is one of: a non-empty lowercase string, Z (meaning ZHONGJIANWANGLE), or N. The last segment is one of: a non-empty lowercase string, H (meaning HOUMIANWANGLE), or N. It is guaranteed that among the three segments, exactly one is N.

Output Format

Output one integer in a single line, the maximum number of copies that can be matched among all record strings.

3
N Z H
Q N H
Q Z N

1

Hint

For all data, it is guaranteed that the sum of lengths of all input strings does not exceed $10 ^ 6$.

• Subtask 1 ($20$ points): In each copy, besides NFLSPC#6QIDONG appearing exactly once, all other parts are forgotten. That is, the input copy string can only be one of N Z H, Q N H, Q Z N.
• Subtask 2 ($30$ points): For all copy strings, the back segment is NFLSPC#6QIDONG. That is, each input copy string must be of the form * * N, where * denotes any input that conforms to the format.
• Subtask 3 ($50$ points): No special constraints.

Source: NFLSPC #6 J by Troverld.

Translated by ChatGPT 5