Reconstructing the Original Record

You have discovered n text copies on your computer. In some mysterious way, you feel that they are all copies of a single original record. The original record is a string (possibly empty) containing only lowercase English letters. Each copy is formed by cutting the record into three pieces (each piece may be empty) in a possibly different way; we call these pieces the front, middle, and back segments.

However, in some copies one or more segments might have been completely forgotten. Specifically, if the front segment was forgotten it is represented by QIANMIANWANGLE, if the middle segment was forgotten it is represented by ZHONGJIANWANGLE, and if the back segment was forgotten it is represented by HOUMIANWANGLE. For a copy, a segment is considered recorded if it is not replaced by its corresponding marker, and forgotten otherwise.

A record matches a copy if you can partition the record into three parts (not necessarily uniquely) so that for each segment the following holds:

• If the copy’s segment is recorded then the corresponding part of the record must be exactly the same.
• If the copy’s segment is forgotten then any lowercase string (even empty) is allowed in that position.

In particular, note that if both the front and back segments are recorded and the middle segment is recorded as well, the record is forced to be exactly the concatenation:
\(\text{front} + \text{middle} + \text{back}\).
If only a prefix is given (that is, the copy recorded the front segment while the middle was forgotten), the record only needs to start with that front string; similarly, if only the back is provided, the record only needs to end with that back string; if only the middle is provided, the record must contain that string as a substring.

Your goal is to choose a record (you do not need to output it) so that as many copies as possible match it. Compute the maximum number of copies that can be matched by some record.

---

Note: Any formulas in this statement are formatted in \(\LaTeX\). For example, if all three segments are provided, a matching record must satisfy \(R = \text{front} + \text{middle} + \text{back}\).

inputFormat

The first line contains an integer n (the number of copies). Each of the following n lines contains three strings separated by spaces, representing the front, middle, and back segments of a copy respectively. A segment may be an empty string. However, if a segment is forgotten it is exactly one of:

• QIANMIANWANGLE (front forgotten)
• ZHONGJIANWANGLE (middle forgotten)
• HOUMIANWANGLE (back forgotten)

All recorded segments (i.e. those not equal to their marker) consist solely of lowercase English letters.

outputFormat

Output a single integer, the maximum number of copies that can be matched by some record.

sample

3
abc def ghi
abc def HOUMIANWANGLE
QIANMIANWANGLE xyz HOUMIANWANGLE

2