题目描述

二十一世纪是生物技术飞速发展的世纪。其中最具吸引力和挑战性的任务之一是基因项目，尤其是基因排序程序。我们知道基因由$DNA$ 组成，而构建 $DNA$ 的核苷酸碱基有腺嘌呤（$A$）、胞嘧啶（$C$）、鸟嘌呤（$G$）和胸腺嘧啶（$T$）。给定几个基因片段，要求你用这些片段组成一个最短的序列，该序列需使用所有片段，且不能翻转任何片段。

例如，给定片段 'TCGG'、'GCAG'、'CCGC'、'GATC' 和 'ATCG'，可以按以下方式拼接这些片段得到一个长度为 $11$ 的序列，这是最短的序列（可能不是唯一的）。

输入

第一行是一个整数 $T$（$1 \leq T \leq 20$），表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$（$1 \leq N \leq 10$），表示片段的数量。接下来的 $N$ 行分别表示 $N$ 个片段，假设每个片段的长度在 $1$ 到 $20$ 之间。

输出

对于每个测试用例，输出一行，包含用这些片段组成的最短序列的长度。

输入数据 1

1
5
TCGG
GCAG
CCGC
GATC
ATCG

输出数据 1

11

来源

POJ 月赛 -- 2004.07.18