قرر القزم الرحّالة تركيز اهتمامه هذا العام على غزو قمم فروتسواف. هدفه الأحدث هو غزو $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