בשנת 2077, חיבור בעיות הופך לפשוט. רובוטים ייצרו בעיה על ידי הגדרת כמה פעולות אקראיות ואז יפתרו אותה. מחבר בעיות צריך רק לבדוק האם הבעיה נכונה או לא.

הנה בעיה משנת 2077:

נתונה תמורה $p_1, p_2, \dots, p_n$, ומובטח כי $n$ הוא זוגי. ברצונכם למיין את התמורה תוך שימוש בסוג אחד בלבד של פעולה:

• FakeSort(l,r): עליכם להבטיח כי $r - l + 1$ הוא זוגי. יהי $k = r - l + 1$, אזי $k/2$ האיברים הגדולים ביותר ו-$k/2$ האיברים הקטנים ביותר בתת-הסדרה הרציפה $p_l, p_{l+1}, \dots, p_r$ ימוינו באופן בלתי תלוי. כלומר, יהיו $L_1, L_2, \dots, L_{k/2}$ האינדקסים של $k/2$ המספרים הגדולים ביותר, ו-$S_1, S_2, \dots, S_{k/2}$ האינדקסים של $k/2$ המספרים הקטנים ביותר. תחילה אנו ממיינים את המספרים שבאינדקסים $L_1 \sim L_{k/2}$, ולאחר מכן ממיינים את המספרים שבאינדקסים $S_1 \sim S_{k/2}$.

הנה דוגמה מוחשית; נניח שהתמורה היא $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. אם נקרא ל-FakeSort(2,7):

• $k = r - l + 1 = 6$. תת-הסדרה הרציפה $p_l, p_{l+1}, \dots, p_r$ היא $\{5, 7, 1, 8, 6, 4\}$; נמיין את $3$ המספרים הגדולים ביותר ואת $3$ המספרים הקטנים ביותר של סדרה זו באופן בלתי תלוי.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; $3$ המספרים הגדולים ביותר מודגשים. לאחר המיון הם הופכים ל-$p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; $3$ המספרים הקטנים ביותר מודגשים. לאחר המיון הם הופכים ל-$p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

לכן $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ אחרי FakeSort(2,7) הופכת ל-$\{2, 1, 6, 4, 7, 8, 5, 3\}$.

אנא השתמשו בלא יותר מ-$114$ פעולות כדי למיין את התמורה או קבעו שזה בלתי אפשרי. ניתן להוכיח שאם אפשר למיין תמורה באמצעות פעולה זו, קיימת דרך המשתמשת בלא יותר מ-$114$ פעולות.

קלט

הקלט מכיל מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 10^3$), מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, השורה הראשונה מכילה מספר שלם זוגי $n$ ($4 \le n \le 10^5$), אורך התמורה.

השורה השנייה מכילה $n$ מספרים שלמים $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), התמורה שעליכם למיין. מובטח כי $p$ היא תמורה.

מובטח שסכום ה-$n$-ים על פני כל מקרי הבדיקה אינו עולה על $2 \times 10^5$.

פלט

עבור כל מקרה בדיקה, אם בלתי אפשרי למיין את התמורה, הדפיסו $-1$.

אחרת, הדפיסו מספר שלם $k$ ($0 \le k \le 114$), המציין את מספר הפעולות שבהן נעשה שימוש.

ב-$k$ השורות הבאות, הדפיסו $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ הוא זוגי) בכל שורה, המציינים ביצוע של FakeSort(l,r).

דוגמאות

קלט לדוגמה 1

3
4
2 1 4 3
6
3 6 5 1 2 4
8
3 2 1 7 5 4 6 8

פלט לדוגמה 1

1
1 4
-1
2
4 7
1 6