لدى 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)$.