sng summer camp 1

D. 字串变换

单点时限: 10.0 sec

内存限制: 512 MB

假设对一个字符串可进行以下两种类型的变换:

  1. 对字串中的任意一个字符进行复制。例如:xyz 复制其中一个字符 y 变为 xyyz
  2. 对字串中的相邻的两个相同字符删除其中一个。例如:xxyz 删除其中一个字符 x 变为 xyz

现在给出 $n$ 个字符串,计算最少需要几次以上变换才能使得这 $n$ 个字符串都变得相同。

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行,每行输入一个字符串,由小写字母组成,字符串长度不超过 $100$。

  • 对于 $50\%$ 的数据,$1 \le n \le 100$;
  • 对于 $100\%$ 的数据,$1 \le n \le 10^5$。

输出格式

在每一行中输出所需要的最小变换次数。如果不可能达成目标,则输出 $-1$。

样例

Input
2
abc
bac
Output
-1
Input
3
aaabbb
ab
aabb
Output
4
Input
3
aabbcc
aabbcc
aabbcc
Output
0

提示

例如:有 3 个字串 aaabbbabaabb,需要最少 $4$ 次变换,最后全部变成 aabb