今天帥哥總召要出任務，以下是他詢問大家對字串的看法：

小 A 說：在我看來學會 AC 自動機就夠了，名字有 AC 到處都 AC！

小 S 說：真的嗎？聽說 Suffix array 可以解決 $70\%$ 的字串題欸？不需要會其他的吧？不然字串也太難了，哪那麼雖？

小 O 說：不會啊，字串很簡單啊。 KMP 就是在討論前綴跟前綴的後綴的關係、 Z value 就是在討論前綴跟後綴的前綴的關係、Manacher's algorithm 就是在討論子字串的子字串跟回文的關係！

小 W 說：有道理，所以題目裡出現兩次前綴和一次後綴就用 KMP ，出現回文就用 Manacher's algorithm！

小 M 說：在我看來大家都忽略了一個最強的算法，不管甚麼題目用 Trie 直接 Trie Trie 看就會過了！

小 T 說：也不用那麼麻煩，看到題目直接迴圈掃過去就可以了，反正輸入的字串長度都是有限大，通通都是常數！

小 C 說：現在的題目怎麼都那麼難懂，要是直接告訴我要怎麼做就好了！

帥哥總召要回答的任務如下：

現在一共有 $N$ 個字串 $s_1, s_2, \cdots, s_N$ ，對於一個字串 $p$ 來說，定義這個字串的美麗度的值為滿足條件的二元組 $(k, i)$ 的數量。

一個二元組 $(k, i)$ 滿足條件若且惟若字串 $s_i$ 的前 $k$ 個字元與字串 $p$ 的前 $k$ 個字元拼起來是回文字串，即 $s_{i_0} s_{i_1} s_{i_2} \cdots s_{i_{k - 2}} s_{i_{k - 1}} p_0 p_1 p_2 \cdots p_{k - 2} p_{k - 1}$ 是回文字串。

接著給出一個長度限制 $L$，請算出對於所有每個可能的 $x$ 滿足 $1 \le x \le L$ ，一個長度為 $x$ 的未知字串 $p$ 最大可能的美麗度是多少？