يلعب 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$