הגמד המטייל החליט למקד השנה את תשומת ליבו בכיבוש הפסגות של ורוצלב. היעד העדכני שלו הוא לכבוש $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