ל־Little Cyan Fish יש תמורה $p_1, p_2, \ldots, p_n$ של המספרים השלמים מ־$1$ עד $n$, וכפי שמרמזת כותרת הבעיה, הוא רוצה למיין אותה בסדר עולה. הפעם, הפעולה שהוא יכול לבצע היא כדלקמן.

• בפעולה אחת, Little Cyan Fish רשאי לבחור שני מספרים שלמים $i$ ו־$j$ כך ש־$1 \le i < j \le n$ ולהחליף בין $p_i$ ל־$p_j$.

אבל נו באמת, כולם יודעים איך למיין תמורה באמצעות החלפות פשוטות, כך שברור שזה לא מה שהמשימה מבקשת מכם לעשות. במקום זאת, Little Cyan Fish מגדיר את המרחק של פעולה להיות $j - i$. עבור סדרת פעולות שממיינת את התמורה, נסמן ב־$a_d$ את מספר הפעולות ממרחק $d$, לכל $1 \le d < n$.

מבין כל סדרות הפעולות הסופיות שממיינות את התמורה, Little Cyan Fish רוצה שתמצאו את הסדרה הקטנה ביותר לקסיקוגרפית $(a_1, a_2, \ldots, a_{n-1})$, ותבנו סדרה של לכל היותר $5n$ פעולות שמשיגה אותה.

קלט

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

עבור כל מקרה בדיקה, השורה הראשונה מכילה מספר שלם יחיד $n$ ($2 \le n \le 10^6$), המציין את אורך התמורה. השורה השנייה מכילה $n$ מספרים שלמים $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), המציינים את התמורה. מובטח כי $p$ היא תמורה באורך $n$.

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $10^6$.

פלט

עבור כל מקרה בדיקה, הדפיסו את התשובה בפורמט הבא.

השורה הראשונה עבור כל מקרה בדיקה צריכה להכיל $n - 1$ מספרים שלמים $a_1, a_2, \ldots, a_{n-1}$, הסדרה הקטנה ביותר לקסיקוגרפית.

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

כל אחת מ־$k$ השורות הבאות צריכה להכיל שני מספרים שלמים $i$ ו־$j$ ($1 \le i < j \le n$), האינדקסים שנבחרו בפעולה המתאימה. הפעולות, כאשר הן מבוצעות בסדר הנתון, חייבות למיין את תמורת הקלט, ולכל $1 \le d < n$, בדיוק ל־$a_d$ מהפעולות חייב להיות מרחק $d$.

ניתן להראות שתמיד קיימת סדרה אופטימלית של לכל היותר $5n$ פעולות. אם קיימות מספר סדרות חוקיות של פעולות, תוכלו להדפיס כל אחת מהן.

דוגמאות

קלט 1

3
3
3 2 1
4
2 1 3 4
4
1 3 2 4

פלט 1

0 1
1
1 3
0 1 2
3
1 4
2 4
1 4
0 3 2
5
1 3
1 4
2 4
1 4
1 3

הערה

במקרה הבדיקה הראשון בדוגמה, Little Cyan Fish מחליף בין המיקומים $1$ ו־$3$. פעולה זו ממיינת את התמורה באמצעות פעולה אחת ממרחק $2$.

במקרה הבדיקה השני בדוגמה, סדרה אופטימלית אחת היא $(1, 4)$, $(2, 4)$, $(1, 4)$. המרחקים הם $3$, $2$ ו־$3$, ולכן הסדרה המתקבלת היא $(0, 1, 2)$.

במקרה הבדיקה השלישי בדוגמה, סדרה אופטימלית אחת היא $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. מספרי הפעולות שלה לפי מרחק הם $(0, 3, 2)$.