Type: Default 1000ms 256MiB

进化论

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

进化论,生物学术语。是由英国生物学家查尔斯·达尔文(1809—1882)曾经乘坐贝格尔号舰作了历时 55 年的环球航行中,对动植物和地质方面进行了大量的观察和采集后,当时是对物种起源的一种猜测而提出的一种假说。随着进化论的发展,产生了现代综合进化论,而现代进化学绝大部分以查尔斯·罗伯特·达尔文的进化论为指导,埃尔温·薛定谔的《生命是什么》为主体方向,进化论已为当代生物学的核心思想之一。

所有生物物种是由少数共同祖先,经过长时间的自然选择过程后演化而成。2018年诺贝尔化学奖:定向进化技术是进化论的具体应用和实现。

古希腊时期曾出现零星的进化思想,包括现在“进化论”者的进化无方向存在即合理,都不具有系统性的科学性。

题目描述

如今的生物种类均变幻莫测。因此,科学家们使用 AZ, azA\sim Z,~a\sim z 为每种生物的基因进行编号。已知现在共有 nn 个物种,每个物种拥有一个长度为 LiL_i 的基因编码。随着科技的发展,人类已经不再拘泥于发现物种,而在于利用基因编辑重新创造物种,或者换句话说,克隆。所以,对于已经具有的基因序列,人类可以通过编辑将其转换为另一个序列。

当然,基因编辑显然需要一定的代价。对于两个物种,基因编辑的代价为两物种基因序列所具有的不同字母的数量(严格区分大小写,但不考虑位置)。如今人们已经具有了第一种生物的基因序列。请问最少付出多少代价能使得人类掌握全部的基因序列。

注意“具有”意味着人类可以多次使用某个基因序列,即基因序列本身不会因为编辑而改变,编辑的作用在于创造新的序列。

输入格式

第一行为一个正整数 TT,表示数据组数。

对于每组数据,第一行为一个正整数 nn,表示物种的数量。接下来 nn 行,每行包含一个正整数 LiL_i 和一个长度为 LiL_i 的字符串 SiS_i,表示物种的基因序列。

输出格式

TT 行,对于每组数据,输出一个整数表示最少付出的代价。

2
3
3 ABC
3 DEF
3 DGH
8
6 ABCFGE
5 AHSDF
6 SDAOFM
7 OPaAion
6 abcfgE
5 ADjdn
6 KLAdpO
7 OPSDFAM
11
61

说明

对于 30%30\% 的数据,n100n≤100

对于 100%100\% 的数据,2n1032≤n≤10^31T31≤T≤31Li501≤L_i≤50{Si}{AZ  az}\{S_i\}∈\{A\sim Z\ \cup\ a\sim z\}

请尽可能避免因 \n 不兼容而造成的读入错误。

  • 第一个物种到第二个物种的代价为 {ABCDEF}=6\{\text{ABCDEF}\}=6
  • 第一个物种到第三个物种的代价为 {ABCDGH}=6\{\text{ABCDGH}\}=6
  • 第三个物种到第二个物种的代价为 {DGHEF}=5\{\text{DGHEF}\}=5

所以顺序为 1231\to 2\to 3,最少代价为 6+5=116+5=11