Missing Bigram
Contest: Codeforces Round 760 (Div. 3)
Difficulty rating: 800
Tags: implementation

Polycarp has come up with a new game to play with you. He calls it "A missing bigram".

A bigram of a word is a sequence of two adjacent letters in it.

For example, word "abbaaba" contains bigrams "ab", "bb", "ba", "aa", "ab" and "ba".

The game goes as follows. First, Polycarp comes up with a word, consisting only of lowercase letters 'a' and 'b'. Then, he writes down all its bigrams on a whiteboard in the same order as they appear in the word. After that, he wipes one of them off the whiteboard.

Finally, Polycarp invites you to guess what the word that he has come up with was.

Your goal is to find any word such that it's possible to write down all its bigrams and remove one of them, so that the resulting sequence of bigrams is the same as the one Polycarp ended up with.

The tests are generated in such a way that the answer exists. If there are multiple answers, you can print any of them.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the length of the word Polycarp has come up with.

The second line of each testcase contains $$$n-2$$$ bigrams of that word, separated by a single space. Each bigram consists of two letters, each of them is either 'a' or 'b'.

Additional constraint on the input: there exists at least one string such that it is possible to write down all its bigrams, except one, so that the resulting sequence is the same as the sequence in the input. In other words, the answer exists.

Output format:
For each testcase print a word, consisting of $$$n$$$ letters, each of them should be either 'a' or 'b'. It should be possible to write down all its bigrams and remove one of them, so that the resulting sequence of bigrams is the same as the one Polycarp ended up with.

The tests are generated in such a way that the answer exists. If there are multiple answers, you can print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first two testcases from the example are produced from the word "abbaaba". As listed in the statement, it contains bigrams "ab", "bb", "ba", "aa", "ab" and "ba".

In the first testcase, the $$$5$$$-th bigram is removed.

In the second testcase, the $$$2$$$-nd bigram is removed. However, that sequence could also have been produced from the word "abaabaa". It contains bigrams "ab", "ba", "aa", "ab", "ba" and "aa". The missing bigram is the $$$6$$$-th one.

In the third testcase, all of "baa", "aab" and "aaa" are valid answers.

Example input:
4
7
ab bb ba aa ba
7
ab ba aa ab ba
3
aa
5
bb ab bb

Example output:
abbaaba
abaabaa
baa
bbabb

Editorial:
Consider a full sequence of bigrams for some word. The first bigram consists of letters $$$1$$$ and $$$2$$$ of the word. The second bigram consists of letters $$$2$$$ and $$$3$$$. The $$$i$$$-th bigram consists of letters $$$i$$$ and $$$i+1$$$.
After one bigram is removed, there becomes two adjacent bigrams such that one consists of letters $$$i$$$ and $$$i+1$$$ and the other consists of letters $$$i+2$$$ and $$$i+3$$$. Thus, we can find the position of the removed bigram by looking for a pair of adjacent bigrams such that the second letter of the first one differs from the first letter of the second one.
If there is no such pair, then the sequence of bigrams represents a valid word of length $$$n-1$$$. We can append it with any bigram that starts with the second letter of the last bigram to make it a valid word of length $$$n$$$.
If there exists such a pair, then all letters of the word can be recovered. We can find the position of the removed bigram, determine the letters it consisted of and insert it into the sequence.
After that, we have a full sequence of bigrams and we can restore the word from it.
Overall complexity: $$$O(n)$$$ per testcase.