Finding the Unforgettable Record

You have a very important record string that must never be forgotten. Unfortunately, after the invasion of the 1064 virus your computer lost it – and even scarred your memory of it! Fortunately, before the virus infection you made n copies of the record. Each copy was obtained by arbitrarily splitting the record string (of unknown length) into three non‐empty parts in order: prefix, middle, and suffix.

However, during the splitting process you were affected by the 1064 virus and, in some copies, some parts were completely forgotten. In particular, the prefix part may be replaced by QIANMIANWANGLE, the middle part by ZHONGJIANWANGLE, and the suffix part by HOUMIANWANGLE. In a copy, if a segment was replaced by one of these markers then that segment is considered forgotten; otherwise, it is remembered exactly as it originally was.

You clearly recall one thing: in the original record string, the substring NFLSPC#6QIDONG appears exactly once as a contiguous block; besides that substring, every other character is a lowercase English letter. Moreover, when you split the string the remembered copy of one segment accidentally turned out to be exactly NFLSPC#6QIDONG – and your computer also faithfully recorded that segment. Consequently, every copy stored on your computer consists of three non‐empty parts (in order: prefix, middle, suffix) with the following properties:

• Exactly one of the three parts is NFLSPC#6QIDONG.
• The other two parts are either a non‐empty string of lowercase English letters or, if forgotten, they appear as the corresponding virus marker (QIANMIANWANGLE for prefix, ZHONGJIANWANGLE for middle, HOUMIANWANGLE for suffix).

The 1064 virus may have tampered with some information but you are sure that it didn’t change too much – the copies still satisfy all of the above properties. Your goal now is to recover the original record string S (you don’t actually need S – only the maximum number of copies it can match).

A record string S (which consists of lowercase letters except for precisely one occurrence of NFLSPC#6QIDONG) is said to match a copy if S can be split into three non‐empty parts A, B, C (in order) such that:

1. Exactly one of A, B, C is exactly NFLSPC#6QIDONG and the other two consist solely of lowercase letters.
2. For each copy and for each part, either the copy’s part is exactly the same as the corresponding one of A, B, C, or the copy’s part is forgotten (i.e. it is the appropriate virus marker).

Your task is to choose a record string S (by implicitly choosing a triple (A, B, C) satisfying the restrictions) so that the number of copies matched is maximized. Output this maximum possible number.

Note on LaTeX formulas: If you need to refer to math formulas, write them in LaTeX format – for example, use $n$ for the number of copies.

inputFormat

The first line contains a positive integer n ($1\le n\le 10^5$), the number of copies.

Each of the next n lines contains three non‐empty strings separated by spaces, representing the prefix, middle, and suffix parts of one copy. In each copy, exactly one part is NFLSPC#6QIDONG and the other two parts are either a non‐empty string of lowercase English letters or the corresponding virus marker (QIANMIANWANGLE for prefix, ZHONGJIANWANGLE for middle, HOUMIANWANGLE for suffix).

outputFormat

Output a single integer – the maximum number of copies that can be simultaneously matched by some valid record string S.

sample

5
NFLSPC#6QIDONG abc def
ghi NFLSPC#6QIDONG def
lmn opq NFLSPC#6QIDONG
QIANMIANWANGLE bcd HOUMIANWANGLE
QIANMIANWANGLE bcd HOUMIANWANGLE

2