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$ จะต้องมีการดำเนินการที่มีระยะทาง $d$ อยู่ $a_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)$