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$