"strcmp()" Anyone?

**【题意】** 共 $T$ 组数据，每组数据给出 $n$ 个字符串 $S_i$。对于每组数据，询问 $\sum_{i=1}^n\sum_{j=i+1}^n cnt(\operatorname{strcmp}(i,j))$ 的值。其中 $cnt(\operatorname{strcmp}(i,j))$ 表示对 $S_i,S_j$ 执行一次 $\operatorname{strcmp}$ 函数需要的比较次数，$\operatorname{strcmp}$ 的实现如下： ```cpp int strcmp(char *s, char *t) { int i; for (i=0; s[i]==t[i]; i++) if (s[i]=='\0') return 0; return s[i] - t[i]; } ``` 注意并不读入 $T$，当 $n=0$ 时表示输入停止。对于第 $i$ 组数据，输出格式为 `Case i: Ans`，其中 `Ans` 表示该组数据对应的答案。 **【数据范围】** $1\le T\le 10$，$1\le n\le4\times10^3$，$1\le |S|\le10^3$，$\Sigma=\{\mathtt{a\sim z},\mathtt{A\sim Z},\mathtt{0\sim 9}\}$，其中 $\Sigma$ 表示可能在 $S$ 中出现的字符集合

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2832 [PDF](https://uva.onlinejudge.org/external/117/p11732.pdf) 



2
a
b
4
cat
hat
mat
sir
0

Case 1: 1
Case 2: 6