Longest Palindrome

All submissions for this problem are available.
Farzi Coder wants to give a nice Christmas present to his brother. For that he has brought N pairs of letters where each letter is either 'a' or 'b'. So, the possible pairs are "aa", "ab", "ba" or "bb". Now, Farzi Coder's brother loves palindromes. So, he decided to concatenate some of the pairs (possibly all or none) and form a palindrome. He wants the longest such palindrome possible. If there are multiple such longest palindromes possible, he wants to give his brother the lexicographically smallest palindrome among them as the gift. Since he is, well, Farzi Coder, you have to help him build the gift.
Input
The first line of the input has the number T denoting the number of test cases.
The first line of each test case has the number N denoting the number of pairs in this case.
Each of the next N lines contain a pair of characters which are either aa, ab, ba or bb.
Output
For each test case, output on a seperate line the gift that Farzi Coder has to build. Note that the empty string is a palindrome.
Constraints
 1 ≤ T ≤ 500
 1 ≤ N ≤ 2000
 Each pair can be either aa, ab, ba or bb
Sample
Input
2 4 aa aa bb bb 3 ab ba ab
Output
aabbbbaa abba
Explanation
Case 1: The following palindromes are possible: "aa", "aaaa", "bb", "bbbb", "aabbaa", "bbaabb", "aabbbbaa", "bbaaaabb". Of these, "aabbbbaa" and "bbaaaabb" are of the maximum length. Among these two, "aabbbbaa" is the lexicographically smallest.
Case 2: The palindromes possible here are: "baab" and "abba".
Author:  balajiganapath 
Editorial  http://discuss.codechef.com/problems/AMLPALIN 
Tags  acm15amr, adhoc, balajiganapath, greedy 
Date Added:  20122015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 