문제1246--가장 큰 수 만들기

1246: 가장 큰 수 만들기

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

음이 아닌 일련의 정수가 주어졌을 때, 이 수들을 조합하여 만들 수 있는 가장 큰 수를 찾아 주세요. 예를 들어 [10, 2]가 주어지면 102, 210 두 개의 수를 만들 수 있는데, 이 중 가장 큰 수는 210입니다.

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=1,000)가 주어집니다. 그다음부터는 각 테스트케이스가 두 줄로 주어집니다. 첫 줄에는 정수의 개수 N(1<=N<=100)이 주어지고, 그다음 줄에는 N개의 정수 X(0<=X<=1,000,000,000)이 주어집니다.

출력 설명

각 테스트케이스마다 주어진 수들을 조합하여 만들 수 있는 가장 큰 수를 출력해 주세요.

입력 예시 Copy

2
2
10 2
5
3 30 34 5 9

출력 예시 Copy

210
9534330

도움

최종 답에 해당하는 수가 너무 크기 때문에 정수나 부동소수 타입으로 표현할 수 없습니다. 문자열로 수를 만들어 출력해야 합니다.