거듭제곱 탑 2: 더 어려운 거듭제곱

참고: 원래는 실제 대회에 이 문제를 내려고 했지만, 내일 풀 좋은 문제가 이미 많고 이 문제는 너무 쉬워서 예행연습(dress rehearsal)에 먼저 공개하기로 했습니다.

이 문제에서는 수를 정렬하는 방법을 다룹니다. 대부분 정렬 알고리즘을 한 번쯤 작성해 봤을 것입니다. 혹시 모르니 간단히 말하면, 작은 수가 앞에 오고 큰 수가 뒤에 오도록 수를 재배열하는 것입니다.

정수가 여러 개 주어집니다. 같은 정수들을 정렬된 순서로 출력하세요. 함정이 무엇이냐고요? 값이 같은 수가 있다면, 입력에서 먼저 나온 수가 출력에서도 먼저 나와야 합니다. 그 밖에는 특별한 것이 없습니다. 작은 수부터 큰 수 순으로 정렬하면 됩니다.

정수는 꽤 클 수 있습니다. 입력을 짧게 하려고 각 정수는 다음과 같은 '거듭제곱 탑' 형태로 주어집니다.

$a_1^{a_2^{\dots^{a_n}}}$

여기서 $1 \le a_1, a_2, \dots, a_n \le 100$이고 $1 \le n \le 100$입니다. 계산은 위에서 아래로 진행하므로 $a_1^{a_2^{a_3}} = a_1^{(a_2^{a_3})}$입니다.

아직 다 안 끝났나요? 그럼 어서 시작하세요!

각 테스트 케이스의 첫 줄에는 그 케이스에 포함된 정수의 개수 M이 주어집니다 (1 ≤ M ≤ 100). 이어지는 M개의 줄에는 정수가 한 줄에 하나씩 주어집니다. 각 정수는 위에서 설명한 형태로 적히며, 거듭제곱은 캐럿(^)으로 나타내고 공백은 없습니다. 각 정수의 표현에는 1개 이상 100개 이하의 수가 있고, 각 수는 1 이상 100 이하의 정수입니다.

각 테스트 케이스마다 케이스 번호를 출력한 뒤, 정렬된 정수 목록을 원래 형태로 한 줄에 하나씩 출력합니다.