给你 $$$n$$$ 字符串 $$$s_1, s_2, \ldots, s_n$$$,每个字符串由小写和大写英文字母组成。此外,还保证每个字符在每个字符串中最多出现两次。找到这些字符串的最长公共子序列。
如果 $$$t$$$ 可以通过删除几个(可能是零个或全部)符号从 $$$s$$$ 获得,则字符串 $$$t$$$ 是字符串 $$$s$$$ 的子序列。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10$$$) — 字符串的数量。
接下来的 $$$n$$$ 行包含相应的字符串 $$$s_i$$$。每个$$$s_i$$$非空,仅由大小写英文字母组成,并且每个字符串中没有字符出现超过两次。
输出
对于每个测试用例,将答案打印为两行:
在第一行打印最长公共子序列的长度。
在第二行打印最长公共子序列。如果有多个这样的子序列,则打印其中任何一个。
示例
输入 #1
4 2 ABC CBA 2 bacab defed 3 abcde aBcDe ace 2 codeforces technocup
输出 #1
1 A 0 3 ace 3 coc
注意
在第一个测试用例中,最长公共子序列是“A”。不存在长度为 $$$2$$$ 的公共子序列。
在第二个测试用例中,字符串的字符集不相交,因此任何非空字符串都不能是公共子序列。