영어 알파벳 대문자로만 구성된 문자열이 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인 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줄에 걸쳐 한 줄에 하나씩 영문 알파벳 대문자로만 구성된 문자열이 주어진다.

출력 형식

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

예제 입력

2
3
ABC
ABD
XY
3
ABC
XC
DZ

예제 출력

000
001

힌트

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