Jelefy กำลังเล่นหอคอยแห่งฮานอยโดยมีกติกาพิเศษ

หอคอยแห่งฮานอยมีเสาสามต้น ได้แก่ $A$, $B$ และ $C$ ซึ่งสามารถวางซ้อนจานกลมได้ จานกลมสามารถย้ายไปมาระหว่างเสาต่าง ๆ ได้ แต่ต้องปฏิบัติตามกติกาต่อไปนี้:

• ย้ายจานกลมได้เพียงครั้งละหนึ่งใบเท่านั้น;
• ในแต่ละครั้งสามารถย้ายได้เฉพาะจานกลมใบบนสุดของเสาต้นหนึ่งไปยังด้านบนสุดของเสาอีกต้นหนึ่งเท่านั้น;
• บนเสา $B$ และ $C$ ห้ามวางจานกลมใบใด ๆ ทับบนจานกลมที่มีขนาดเล็กกว่า;
• บนเสา $A$ สามารถวางจานกลมที่มีขนาดใหญ่กว่าทับบนจานกลมที่มีขนาดเล็กกว่าได้

ในตอนเริ่มต้น Jelefy สุ่มวางซ้อนจานกลมขนาดแตกต่างกันจำนวน $n$ ใบบนเสา $A$ และปล่อยให้เสา $B$ และ $C$ ว่างเปล่า ภายใต้เงื่อนไขข้างต้น Jelefy ต้องการทราบว่าต้องใช้การย้ายกี่ครั้งจึงจะย้ายจานกลมทั้งหมดจากเสา $A$ ไปยังเสา $B$ ได้

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1\leq T\leq 10^4$) แทนจำนวนชุดข้อมูลทดสอบ

สำหรับแต่ละชุดข้อมูลทดสอบ: บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($1\leq n\leq 10^5$) แทนจำนวนจานกลมบนเสา $A$ ในสถานะเริ่มต้น

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน ได้แก่ $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$) โดยที่ $p_i$ แทนเส้นผ่านศูนย์กลางของจานกลมใบที่ $i$ บนเสา $A$ นับจากล่างขึ้นบน รับประกันว่า $p_1,p_2,\ldots,p_n$ เป็นการเรียงสับเปลี่ยนความยาว $n$ กล่าวคือ จำนวนเต็มแต่ละตัวตั้งแต่ $1$ ถึง $n$ จะปรากฏในลำดับเพียงหนึ่งครั้งเท่านั้น

สำหรับทุกชุดข้อมูลทดสอบ รับประกันว่า $\sum n\leq 2\times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์จำนวนเต็มหนึ่งจำนวนในบรรทัดเดียว แทนจำนวนครั้งของการย้ายที่น้อยที่สุดที่ต้องใช้

ตัวอย่าง

ข้อมูลนำเข้า 1

3
5
1 5 3 2 4
5
1 2 3 4 5
6
5 3 6 1 4 2

ข้อมูลส่งออก 1

11
5
19

หมายเหตุ

ในตัวอย่างแรก วิธีการหนึ่งที่เป็นไปได้ซึ่งใช้จำนวนครั้งในการย้ายน้อยที่สุดมีดังนี้ ($X\rightarrow Y$ หมายถึงการย้ายจานกลมใบบนสุดจากเสา $X$ ไปยังด้านบนสุดของเสา $Y$):

• $A\rightarrow C$
• $A\rightarrow B$
• $A\rightarrow C$
• $B\rightarrow C$
• $A\rightarrow B$
• $C\rightarrow A$
• $C\rightarrow A$
• $C\rightarrow B$
• $A\rightarrow B$
• $A\rightarrow B$
• $A\rightarrow B$