天才间谍鲍勃截获了一条加密消息。他认为其中包含秘密信息,并积极致力于破译它。
这张纸条已落入间谍手中,由 $$$k$$$ 条组成,每条长度为 $$$n$$$,并包含严格的小写拉丁字母。凭借破译此类文档的丰富经验,Bob 猜测他感兴趣的消息(破译纸条)也是一串长度为 $$$n$$$ 的字符串,并且该消息的第 $$$i$$$ 个字母对应于其中一个条带的第 $$$i$$$ 个字母。
根据鲍勃的说法, 信息量 字符串$$$s$$$的 被定义为最小正整数$$$d$$$,使得长度为$$$d$$$的字符串$$$t$$$存在,并且$$$s$$$可以通过多次重复$$$t$$$来形成。例如,字符串“的信息量”啊啊啊“为1,字符串的信息量”abab“为2,字符串的信息量”abcd”是 4。
Bob 假定该注释的作者为了确保信息的可靠传输,多次重复了消息中的数据。因此,他认为对纸条进行更合理的解密将具有尽可能小的信息量。
帮助间谍:找到代表笔记解密且信息量尽可能小的消息。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
在每个测试用例的第一行,有数字 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n, k \leq 50\,000, 4 \leq n \cdot k \leq 10^5$$$) — 纸条的长度和纸条的数量。
在每个测试用例的以下 $$$k$$$ 行中,都有一个 $$$n$$$ 小写拉丁字母序列 - 下一个条带。
保证所有测试用例的总和 $$$n \cdot k$$$ 不超过 $$$10^5$$$
输出
对于每个测试用例,输出一个长度为 $$$n$$$ 的字符串 - 注释的解密,其具有尽可能小的信息量。如果有多个合适的答案,则可以输出其中任何一个。
示例
输入复制
33 2abcbaa9 2iiinnnfffnnfiffinn4 2acbdbdac
输出复制
aaainfinfinfacac
注意
在第一个测试用例中,最小可能的信息量为 $$$1$$$:
abc
baa
在第二个测试用例中,最小可能的信息量为 $$$3$$$:
i我在nnfff
nnfiffinn