题目描述

Polycarp 想出了一个新游戏，叫做“缺失的二元组”。

一个单词的二元组是指该单词中相邻的两个字母组成的序列。

例如，单词 "abbaaba" 包含的二元组有 "ab"、"bb"、"ba"、"aa"、"ab" 和 "ba"。

游戏规则如下：首先，Polycarp 想出一个只包含小写字母 'a' 和 'b' 的单词。然后，他按顺序将该单词的所有二元组写在白板上。接着，他擦掉其中的一个二元组。

最后，Polycarp 邀请你来猜他原本想出的单词是什么。

你的目标是，找出任意一个单词，使得可以写出它的所有二元组，并移除其中一个二元组后，剩下的二元组序列与 Polycarp 最终留下的序列完全一致。

测试数据保证答案一定存在。如果有多个答案，你可以输出任意一个。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 100$），表示 Polycarp 想出的单词的长度。

每个测试用例的第二行包含 $n-2$ 个该单词的二元组，二元组之间用一个空格分隔。每个二元组由两个字母组成，每个字母都是 'a' 或 'b'。

输入有额外保证：至少存在一个字符串，可以写出它的所有二元组，并移除其中一个二元组后，剩下的序列与输入序列一致。换句话说，答案一定存在。

输出格式

对于每个测试用例，输出一个由 $n$ 个字母组成的单词，每个字母都是 'a' 或 'b'。要求能够写出它的所有二元组，并移除其中一个二元组后，剩下的二元组序列与 Polycarp 最终留下的序列完全一致。

测试数据保证答案一定存在。如果有多个答案，你可以输出任意一个。

说明/提示

示例中的前两个测试用例来源于单词 "abbaaba"。如题目所述，它包含的二元组为 "ab"、"bb"、"ba"、"aa"、"ab" 和 "ba"。

在第一个测试用例中，第 $5$ 个二元组被移除了。

在第二个测试用例中，第 $2$ 个二元组被移除了。不过，该序列也可以由单词 "abaabaa" 得到。它包含的二元组为 "ab"、"ba"、"aa"、"ab"、"ba" 和 "aa"。缺失的是第 $6$ 个二元组。

在第三个测试用例中，"baa"、"aab" 和 "aaa" 都是有效答案。

由 ChatGPT 4.1 翻译

样例

4
7
ab bb ba aa ba
7
ab ba aa ab ba
3
aa
5
bb ab bb

abbaaba
abaabaa
baa
bbabb