{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"题目描述","value":{"format":"PLAIN","content":"21世纪是生物科技飞速发展的时代。我们都知道基因是由DNA组成的,而DNA的基本组成单位是A,C,G,T。在现代生物分子计算中,如何找到DNA之间的最长公共子序列是一个基础性问题。\n但是我们的问题不是那么简单:现在我们给定了数个DNA序列,请你构造出一个最短的DNA序列,使得所有我们给定的DNA序列都是它的子序列。\n例如,给定\"ACGT\",\"ATGC\",\"CGTT\",\"CAGT\",你可以构造的一个最短序列为\"ACAGTGCT\",但是需要注意的是,这并不是此问题的唯一解。"}},{"title":"输入","value":{"format":"PLAIN","content":"第一行含有一个数t,代表数据组数。\n每组数据的第一行是一个数n,代表给定的DNA序列数量;接下来的n行每行一个字符串s,代表给定的n个DNA序列。\n1\u003c\u003dn\u003c\u003d8,1\u003c\u003d|s|\u003c\u003d5"}},{"title":"输出","value":{"format":"PLAIN","content":"对于每一组数据,输出一行中含有一个数,代表满足条件的最短序列的长度。"}},{"title":"样例输入","value":{"format":"PLAIN","content":"1\n4\nACGT\nATGC\nCGTT\nCAGT"}},{"title":"样例输出","value":{"format":"PLAIN","content":"8"}}]}