문자열 뒤집기

영어 대문자로만 이루어진 문자열이 N개 있다. 이를 S[1], S[2], ..., S[N]이라 하자.

Reverse(T)는 임의의 문자열 T를 뒤집은 문자열이다. 모든 문자열 T에 대해 Reverse(Reverse(T)) = T가 성립한다.

예를 들어 Reverse("ABC") = "CBA"이다.

N개의 문자열 각각에 Reverse()를 적용할지 말지를 정할 수 있다. 이렇게 해서 문자열이 사전순으로 정렬되도록 하려 한다. 문자열이 N개이므로 모두 2^N가지 방법이 있다.

각 문자열에 Reverse()를 적용한 경우를 '1', 적용하지 않은 경우를 '0'으로 나타내면 길이 N의 0-1 문자열이 된다. 이를 "리버스 문자열"이라 하자.

예를 들어 N = 3이고 S[1] = "ABC", S[2] = "XC", S[3] = "DZ"라 하자.

• 리버스 문자열이 "000"인 경우: 세 문자열은 원래 문자열인 "ABC", "XC", "DZ"가 되고 사전순으로 정렬되지 않는다 (S[3]이 S[2]보다 앞선다).
• 리버스 문자열이 "001"인 경우: 3번 문자열에만 Reverse()를 적용하면 세 문자열은 "ABC", "XC", "ZD"가 되어 사전순으로 정렬된다.
• 리버스 문자열이 "010"인 경우: 2번 문자열에만 Reverse()를 적용하면 세 문자열은 "ABC", "CX", "DZ"가 되어 사전순으로 정렬된다.
• 리버스 문자열이 "101"인 경우: 1번과 3번 문자열에 Reverse()를 적용하면 "CBA", "XC", "ZD"가 되어 사전순으로 정렬된다.

이 외에도 다른 방법으로 세 문자열을 사전순으로 정렬할 수 있다.

입력으로 주어진 N개의 문자열을 사전순으로 정렬하는 리버스 문자열이 항상 존재한다는 가정하에, 그러한 리버스 문자열 중 사전순으로 가장 앞서는 리버스 문자열을 출력하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에 문자열의 수 N이 주어진다.

다음 N줄에 걸쳐 한 줄에 하나씩 영어 대문자로만 이루어진 문자열이 주어진다.

각 테스트 케이스에 대해 조건을 만족하는 리버스 문자열 중 사전순으로 가장 앞서는 리버스 문자열을 출력한다.

• 1 ≤ T ≤ 50
• 2 ≤ N ≤ 150
• 2 ≤ Length(S[i]) ≤ 20
• 임의의 i ≠ j에 대하여 Reverse(S[i]) ≠ S[j]와 S[i] ≠ S[j]가 항상 성립한다.
• 입력으로 주어지는 모든 케이스에 대해, 주어진 문자열을 사전순으로 정렬하는 리버스 문자열이 항상 존재한다.

사전식 순서: 두 문자열 S, T가 주어졌을 때 S가 T의 prefix이거나, S와 T를 비교했을 때 처음으로 다른 문자가 각각 s, t이고 s가 t보다 사전순으로 앞서는 경우 S가 T보다 사전순으로 앞선다고 한다.