题目描述

无向图中的汉密尔顿是指一条路径，它经过每个点有且仅有一次。每条汉密尔顿路径的权值定义为这条路径中每条边的权值之和。这是最近 WZK 教小 Y 学的图论知识，现在 WZK 想检验一下小 Y 的举一反三的能力，提出了以下问题：

有一个 $n$ 个顶点的无向图（顶点从 $0$ 到 $n-1$ 标号），它的每一个顶点都标有一个字符串$label_i$，两两顶点间都存在一条边，一条从 $i$ 到 $j$ 的边的权值定义为 $length(label_i)^2+length(label_j)^2-length(LCP(label_i,label_j))^2$，$LCP(A,B)$ 指的是 $A,B$ 两个字符串的最长公共前缀。现在，要求一个从顶点 $0$ 出发，到顶点 $1$ 结束的权值最小的汉密尔顿路径。

输入格式

第一行，一个整数 $n$。 接下来 $n$ 行，每行一个不超过 $50$ 个字母的小写字符串 $label_i$，$i$ 从 $0$ 到 $n-1$。

输出格式

仅一行，为要求的汉密尔顿路径的权值。

样例输入

4
abcd
aecgh
abef
aecd

样例输出

91

数据规模与约定

$2\le n\le 50$