Problem D: DNA sequence
Memory Limit：32 MB
Time Limit：5.000 S
Judge Style：Text Compare
Creator：
Submit：9
Solved：6
Description
The twenty-first century is a biology-technology developing century. We know that a gene is made of DNA. The nucleotide bases from which DNA is built are A(adenine), C(cytosine), G(guanine), and T(thymine). Finding the longest common subsequence between DNA/Protein sequences is one of the basic problems in modern computational molecular biology. But this problem is a little different. Given several DNA sequences, you are asked to make a shortest sequence from them so that each of the given sequence is the subsequence of it.
21世纪是一个生物技术发展的世纪。我们知道基因是由DNA构成的。构建DNA的核苷酸碱基是A(腺嘌呤)、C(胞嘧啶)、G(鸟嘌呤)和T(胸腺嘧啶)。寻找DNA/蛋白质序列之间最长的公共子序列是现代计算分子生物学的基本问题之一。但是这个问题有点不同。给定几个DNA序列，你被要求从它们中得到一个最短的序列，这样每个给定的序列就是它的子序列。
For example, given "ACGT","ATGC","CGTT" and "CAGT", you can make a sequence in the following way. It is the shortest but may be not the only one.
例如，给定“ACGT”、“ATGC”、“CGTT”和“CAGT”，您可以通过以下方式生成序列。它是最短的，但可能不是唯一的。
21世纪是一个生物技术发展的世纪。我们知道基因是由DNA构成的。构建DNA的核苷酸碱基是A(腺嘌呤)、C(胞嘧啶)、G(鸟嘌呤)和T(胸腺嘧啶)。寻找DNA/蛋白质序列之间最长的公共子序列是现代计算分子生物学的基本问题之一。但是这个问题有点不同。给定几个DNA序列，你被要求从它们中得到一个最短的序列，这样每个给定的序列就是它的子序列。
For example, given "ACGT","ATGC","CGTT" and "CAGT", you can make a sequence in the following way. It is the shortest but may be not the only one.
例如，给定“ACGT”、“ATGC”、“CGTT”和“CAGT”，您可以通过以下方式生成序列。它是最短的，但可能不是唯一的。
Input
The first line is the test case number t. Then t test cases follow. In each case, the first line is an integer n ( 1<=n<=8 ) represents number of the DNA sequences. The following k lines contain the k sequences, one per line. Assuming that the length of any sequence is between 1 and 5.
第一行是测试样例组数。后面是t个测试样例。
在每个测试样例中，第一行是一个整数n(1<=n<=8)代表DNA序列的数量。后面k行包括k个序列，每个一行。假设任何一个序列的长度都在1到5之间。
第一行是测试样例组数。后面是t个测试样例。
在每个测试样例中，第一行是一个整数n(1<=n<=8)代表DNA序列的数量。后面k行包括k个序列，每个一行。假设任何一个序列的长度都在1到5之间。
Output
For each test case, print a line containing the length of the shortest sequence that can be made from these sequences.
对于每个测试样例，输出一行包括能够组成这些序列的最短序列的长度。
对于每个测试样例，输出一行包括能够组成这些序列的最短序列的长度。
Sample Input Copy
1
4
ACGT
ATGC
CGTT
CAGTSample Output Copy
8