当前没有测试数据。

4.最短字符串

题目描述

有$n$个由$A$，$G$，$C$，$T$组成的小字符串，构造一个大字符串$S$，使得每个小字符串是$S$的子串，最短的串$S$需要多长？

输入格式

第一行输入一个正整数$T$，代表数据的组数。

接下来每组数据先读入一个$n$代表有$n$件事物。

接下来$n$行则是代表每件事物的字符串。

输出格式

对于每一组数据输出一行一个整数代表答案。

数据范围与提示

• 对于$20\%$的数据，$n \leq 2$；
• 对于$100\%$的数据，$T \leq 20$，$n \leq 10$，字符串长度小于$20$。

样例

1
5
TCGG
GCAG
CCGC
GATC
ATCG

11

说明

样例其中一种最优解方案是 CCGCAGATCGG。