该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

以下是本题所用记号的约定。（对字符串比较熟悉的选手可以略过这一部分）

字符串下标均从 $1$ 开始且仅包含小写字母（ASCII 97 ~ 122）。

$|S|$ 表示字符串 $S$ 的长度。$S_i$ 表示字符串 $S$ 的第 $i$ 个字符。

对于字符串 $S,T$，$ST$ 是它们的拼接。例如 $\tt abc$ 和 $\tt qwq$ 的拼接即为 $\tt abcqwq$。

对于字符串 $S,T$，$\operatorname{lcp}(S,T)$ 表示最大的 $x\le\min\{|S|,|T|\}$ 使得对于每个 $i\in[1,x]$ 都有 $S_i=T_i$。

题目描述

对于字符串 $S$，定义 $\operatorname{shuffle}_k(S)$ 是将 $S$ 中的每个字符向后循环移位一位（$\tt a$ 变成 $\tt b$、$\tt b$ 变成 $\tt c$、……、$\tt y$ 变成 $\tt z$、$\tt z$ 变成 $\tt a$）$k$ 次得到的字符串，例如 $\operatorname{shuffle}_1(\texttt{aaacfz})=\texttt{bbbdga},\,\operatorname{shuffle}_2(\texttt{aaacfz})=\texttt{cccehb}$。

对于字符串 $S$ 和非负整数 $k$，按如下方法生成字符串序列 $T$：

进而定义 $S$ 关于 $k$ 的的自描述字符串 $f_k(S)=T_{10^{36}}$。

现在给定 $n$ 个字符串 $S_1,S_2,\cdots,S_n$，构造一个长度为 $n$ 的非负整数序列 $a$，最大化：

的值。你只需要输出最大的 $V$ 即可。如果最大的 $V>10^{18}$ 输出 TAT。

由于某些原因，保证对于每个字符串长度 $\bm{l=|S_i|}$ 都存在自然数 $\bm k$ 使得 $\bm{l=2^k}$ 或 $\bm{l=2^k+2^{k+1}}$。

输入格式

第一行一个正整数 $n$。

后 $n$ 行，第 $i+1$ 行描述字符串 $S_i$。

输出格式

一行一个非负整数或 TAT，表示最大的 $V$ 值。若 $V>10^{18}$ 输出 TAT。

样例 #1

样例输入 #1

2
ab
abcd

样例输出 #1

TAT

样例解释 #1

取 $a_1=4$，$a_2=2$。此时 $f_0(S_1)=\texttt{abcdefgh}\cdots,\,f_2(S_2)=\texttt{abcdefgh}\cdots$。

通过计算可以得到 $\operatorname{lcp}(f_0(S_1),f_2(S_2))=2\times10^{36}+2>10^{18}$，故输出 TAT。

样例 #2

样例输入 #2

5
abc
abca
qwq
qwqw
qwpw

样例输出 #2

15

样例解释 #2

$a$ 序列的一种可能的取值：$[0,1,6,12,0]$，此时每对 $(i,j)$ 所对应 $\operatorname{lcp}(f_{a_j}(S_i),f_{a_i}(S_j))$ 的取值如下：

此时 $V=6+5+2+2=15$。可以证明不存在 $V>15$ 的方案。

数据范围

本题采用捆绑测试。

数据范围：

• Subtask 1 (5pts)：保证存在 $i\neq j$ 使得 $S_i=S_j$。
• Subtask 2 (5pts)：$n\le3$，$|S_i|\le 100$。
• Subtask 3 (30pts)：保证不存在 $i\neq j$ 使得 $S_i$ 不是 $S_j$ 的前缀、且 $S_j$ 不是 $S_i$ 的前缀。
• Subtask 4 (60pts)：无特殊限制。

对于全部数据，$1\le n,\sum|S_i|\le5\times10^5$，字符串仅包含小写字母。