Description

以 GPT 技术为核心的人工智能系统出现后迅速引领了行业的变革，不仅用于大量的语言工作（如邮件编写或文章生成等工作），还被应用在一些较特殊的领域——例如去年就有同学尝试使用 ChatGPT 作弊并被当场逮捕（全校被取消成绩）。相信聪明的你一定不会犯一样的错误！

言归正传，对于 GPT 类的 AI，一个使用方式受到不少年轻用户的欢迎——将 AI 变成猫娘：

部分公司使用 AI 进行网络营销，网友同样乐于使用“变猫娘”的方式进行反击。注意：图中内容与题目无关，如无法看到图片不影响解题。

当然，由于训练数据里并不区分道德或伦理倾向，因此如果不加审查，AI 会生成大量的、不一定符合社会公序良俗的内容。尽管关于这个问题仍有争论，但至少在比赛中，我们还是期望 AI 能用于对人类更有帮助的方向上，少来一点猫娘。

假设现在 deepseek 给你了一个算法以去除内容中的违禁词，但没有给出代码，请你帮助它实现之。

具体而言，deepseek 给你了 $n$ 组违禁词替换，例如：sb 替换成 xka。

deepseek 会按顺序依次将内容中的 $n$ 组违禁词全部替换，只替换一轮显然是不能结束的，因为会出现形如 sb 替换 x，dsb 替换成 bk，而把 sdsb 替换成了 sbk。

我们称一轮替换是从第一组违禁词开始替换，一直替换到第 $n$ 组违禁词，算一轮。

对于每一组违禁词，deepseek 都要替换若干次，直到不存在这一组违禁词。具体而言，令当前字符串为 $S$，$S_l...S_r$ 是 $l$ 最小的满足 $S_l...S_r=a$，则一次替换为 $S=S_1...S_{l-1}bS_{r+1}...S_{|S|}$。

你需要输出最终不需要替换任何违禁词的内容。

数据保证不存在无解的情况。

Format

Input

多组测试数据。

第一行一个正整数 $t(1\le t\le 100)$ 表示数据组数。

对于每组测试数据：

第一行两个正整数 $n,m(1\le m\le 100,2\le n\le 100$ 表示内容字符串长度和替换的违禁词数量，第二行一行一个字符串表示内容。

接下来 $m$ 行，每行两个字符串 $a,b(|a|> |b|\ge 1)$ 表示把违禁词 $a$ 替换成 $b$。

Output

对于每组测试数据输出一行一个字符串表示最终不需要替换任何违禁词的内容。

Samples

1
3 3
aba
a b
b c
c d

ddd