Reversing Strings

There are N strings consisting only of uppercase English letters. Call them S[1], S[2], ..., S[N].

Reverse(T) is the string obtained by reversing an arbitrary string T. For every string T, Reverse(Reverse(T)) = T.

For example, Reverse("ABC") = "CBA".

For each of the N strings, you may choose whether to apply Reverse(). You want the strings to end up sorted in lexicographic order. Since there are N strings, there are 2^N ways to do this.

Write '1' for a string to which Reverse() is applied and '0' for a string to which it is not. This gives a 0-1 string of length N, which we call a "reverse string".

For example, let N = 3, S[1] = "ABC", S[2] = "XC", S[3] = "DZ".

• If the reverse string is "000": the three strings stay "ABC", "XC", "DZ", which is not sorted in lexicographic order (S[3] comes before S[2]).
• If the reverse string is "001": applying Reverse() only to string 3 gives "ABC", "XC", "ZD", which is sorted in lexicographic order.
• If the reverse string is "010": applying Reverse() only to string 2 gives "ABC", "CX", "DZ", which is sorted in lexicographic order.
• If the reverse string is "101": applying Reverse() to strings 1 and 3 gives "CBA", "XC", "ZD", which is sorted in lexicographic order.

There are other ways to sort the three strings in lexicographic order as well.

Assuming that a reverse string sorting the N given strings in lexicographic order always exists, output the lexicographically smallest such reverse string.

The first line gives the number of test cases, T.

The first line of each test case gives the number of strings, N.

The next N lines each contain one string consisting only of uppercase English letters.

For each test case, output the lexicographically smallest reverse string among those that satisfy the condition.

• 1 ≤ T ≤ 50
• 2 ≤ N ≤ 150
• 2 ≤ Length(S[i]) ≤ 20
• For any i ≠ j, Reverse(S[i]) ≠ S[j] and S[i] ≠ S[j] always hold.
• For every case in the input, a reverse string sorting the given strings in lexicographic order always exists.

Lexicographic order: given two strings S and T, S comes before T if S is a prefix of T, or if at the first position where S and T differ the characters are s and t respectively and s comes before t in lexicographic order.