P7861 [COCI 2015/2016 #2] SAVEZ

There is a secret planet S4 where a strange animal lives, whose scientific name is Loda. The Savez association sent a team led by General Henrik to study Loda. Henrik discovered that Loda has the ability of telepathic transmission, and he wants to hire them for his army. One Loda consists of $N$ strings, and the $i$-th string is denoted as $x_i$. Research shows that the number of telepathic transmissions a Loda can perform depends on a special subsequence (not necessarily contiguous) of the strings that make it up. Strings $x_i$ and $x_j\ (i

The first line contains an integer $N$, indicating the total number of strings that make up a Loda. The next $N$ lines each contain a string $x_i$ consisting only of uppercase English letters, representing the strings that make up this Loda.

Output one integer in a single line, indicating how many telepathic transmissions this Loda can perform.

**[Sample 1 Explanation]** One longest subsequence is `A AA AAA`. **[Sample 3 Explanation]** Strings in the subsequence are allowed to be equal, so one longest subsequence is `A A A` or `B B B`. **[Constraints]** For $100\%$ of the testdata, $1\le N \le 2\times 10^6，1\le |x_i| \le 2\times 10^6$, **it is guaranteed that $\sum |x_i|\le 2\times 10^6$**. **[Note]** **The scoring of test cases follows the original problem, with a full score of 120**. Translated from [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T4 SAVEZ**. Translated by ChatGPT 5