{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\n \u003ci\u003eFarzi Coder\u003c/i\u003e wants to give a nice Christmas present to his brother. For that he has brought \u003cb\u003eN\u003c/b\u003e pairs of letters where each letter is either \u0027a\u0027 or \u0027b\u0027. So, the possible pairs are \"aa\", \"ab\", \"ba\" or \"bb\". Now, \u003ci\u003eFarzi Coder\u003c/i\u003e\u0027s 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, \u003ci\u003eFarzi Coder\u003c/i\u003e, you have to help him build the gift.\u003c/p\u003e\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003e The first line of the input has the number \u003cb\u003eT\u003c/b\u003e denoting the number of test cases.\n\u003c/p\u003e\u003cp\u003e\n The first line of each test case has the number \u003cb\u003eN\u003c/b\u003e denoting the number of pairs in this case.\u003c/p\u003e\n\u003cp\u003e\n Each of the next \u003cb\u003eN\u003c/b\u003e lines contain a pair of characters which are either \u003cb\u003eaa\u003c/b\u003e, \u003cb\u003eab\u003c/b\u003e, \u003cb\u003eba\u003c/b\u003e or \u003cb\u003ebb\u003c/b\u003e.\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003e For each test case, output on a seperate line the gift that \u003ci\u003eFarzi Coder\u003c/i\u003e has to build. Note that the empty string is a palindrome.\u003c/p\u003e\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ T ≤ 500\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ N ≤ 2000\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003eEach pair can be either \u003cb\u003eaa\u003c/b\u003e, \u003cb\u003eab\u003c/b\u003e, \u003cb\u003eba\u003c/b\u003e or \u003cb\u003ebb\u003c/b\u003e\n \u003c/li\u003e\n\u003c/ul\u003e\n\u003ch2\u003eSample\u003c/h2\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003c!-- Do not indent input. Will be hard to copy paste --\u003e\u003c!-- Do not indent input. Will be hard to copy paste --\u003e\u003cpre\u003e2\n4\naa\naa\nbb\nbb\n3\nab\nba\nab\n \u003c/pre\u003e\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cpre\u003eaabbbbaa\nabba\n\n \u003c/pre\u003e\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e \u003cb\u003eCase 1:\u003c/b\u003e 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.\u003cbr /\u003e\n \u003cbr /\u003e\u003cbr /\u003e\n \u003cb\u003eCase 2:\u003c/b\u003e The palindromes possible here are: \"baab\" and \"abba\".\u003cbr /\u003e\n \u003cbr /\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\n"}}]}