여행자 드워프는 올해 브로츠와프의 봉우리들을 정복하는 데 집중하기로 결정했습니다. 그의 최신 목표는 연속된 $N$일 동안 매일 정확히 하나의 봉우리씩, 서로 다른 $N$개의 봉우리를 정복하는 것입니다. 여행자에게 봉우리를 정복하는 일은 식은 죽 먹기입니다. 그는 어느 날이든 어떤 봉우리든 정복할 수 있기 때문에, 이번 원정 전체가 언론에 최대한 널리 알려지도록 만들기로 결심했습니다.

드워프는 최근 어떤 규칙을 발견했습니다:

• 첫 번째 봉우리를 정복한 후에는 그 높이와 상관없이 언론의 관심도가 높습니다.
• 어느 날 높이가 $a$인 봉우리를 정복하고 다음 날 높이가 $b$인 봉우리를 정복하면, 그의 원정에 대한 언론의 관심도가 $\lfloor a/b \rfloor$ 단위만큼 감소합니다. 그는 이 단위를 언론 관심도 단위라고 부릅니다.

여행자는 이미 자신이 정복해야 할 $N$개의 봉우리 높이가 $a_1, \dots, a_N$이라는 것을 알고 있습니다. 또한 가장 높은 봉우리의 높이는 가장 낮은 봉우리 높이의 최대 두 배라는 사실이 밝혀졌습니다. 드워프는 봉우리를 방문하는 순서를 임의로 선택할 수 있습니다. 그의 목표는 전체 원정 기간 동안 언론 관심도 단위의 총 감소량을 최소화하는 것입니다.

언론 관심도 단위의 감소량이 최소화되도록 모든 봉우리를 방문하는 순서를 정하는 것을 도와줄 수 있나요?

입력

입력의 첫째 줄에는 테스트 케이스의 개수를 나타내는 수 $T$가 주어집니다.

각 테스트 케이스의 첫째 줄에는 여행자가 방문할 봉우리의 개수를 나타내는 정수 $N$이 주어집니다.

테스트 케이스의 둘째 줄에는 문제에 명시된 조건을 만족하는 $N$개의 정수 $a_1, \dots, a_N$이 주어집니다.

출력

각 테스트 케이스마다 두 줄을 출력합니다. 첫째 줄에는 드워프의 여정에서 언론 관심도 단위의 가능한 최소 감소량을 나타내는 정수를 하나 출력합니다.

둘째 줄에는 이 최소 감소량을 달성하기 위해 드워프가 방문해야 하는 순서대로 배열된 높이 $a_1, \dots, a_N$을 출력합니다.

최적의 해가 여러 개인 경우 아무것이나 출력해도 됩니다.

제한

$1 \le T \le 100\,000, 1 \le N \le 10^6, 1 \le a_i \le 10^9, \max\{a_1, \dots, a_N\} \le 2 \cdot \min\{a_1, \dots, a_N\}$이며, 입력에서 주어지는 $N$의 값들의 합은 $10^6$을 초과하지 않습니다.

예제

입력 1

3
6
10 18 12 13 17 14
4
10 10 7 7
8
8 4 8 5 4 4 8 6

출력 1

0
10 12 13 14 17 18
1
7 10 7 10
4
4 4 4 5 6 8 8 8