책장 정렬

알렉스와 밥은 형제이고 둘 다 책 읽기를 아주 좋아한다. 취향이 크게 달라서 각자 자기 책을 따로 보관한다. 아버지는 두 사람의 책을 한곳에 모아 두면 서로 책을 바꿔 보기 쉬워진다고 생각했다. 그래서 오늘 한 줄짜리 책장을 사 와서 두 아들의 책을 무작위 순서로 모두 꽂았다. 그리고 책장의 자리마다 그 자리에 놓인 책 주인의 이름을 적어 두었다. 이름은 Alex 아니면 Bob이다.

알렉스와 밥은 밖에 나가 있어서 아버지가 한 일을 몰랐다. 돌아와 보니 평소에는 각자의 방식대로 정리해 두던 책이 뒤죽박죽이었다. 둘은 지금 당장 책을 정리해야 한다.

책마다 가치가 있고, 가치는 정수로 나타낸다. 가치가 홀수인 책은 알렉스의 것이고, 가치가 짝수인 책은 밥의 것이다. 알렉스는 자기 책을 왼쪽에서 오른쪽으로 가치가 커지도록 놓는 습관이 있고, 밥은 자기 책을 왼쪽에서 오른쪽으로 가치가 작아지도록 놓는 편을 좋아한다.

동시에 두 사람은 이름표의 자리를 바꾸고 싶어 하지 않는다. 정리를 마친 뒤에도 각 책 주인의 이름이 그 자리의 이름표와 같아야 한다.

책장에 놓인 책의 가치를 왼쪽에서 오른쪽으로 나열한 수열 $s_0, s_1, \dots, s_{N-1}$이 주어진다. 위 규칙대로 정리한 뒤의 가치 수열을 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 책장에 놓인 책의 수 $N$이 주어진다. 다음 줄에는 책의 가치 $s_0, s_1, \dots, s_{N-1}$이 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 30$
• $1 \le N \le 100$
• $-100 \le s_i \le 100$

각 테스트 케이스마다 한 줄을 출력한다. 줄은 Case #X: 로 시작하고, 그 뒤에 정리한 뒤의 가치 $t_0, t_1, \dots, t_{N-1}$을 순서대로 공백 하나로 구분해 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이다.