Jelefy ерекше ережесі бар Ханой мұнарасы ойынын ойнап жатыр.

Ханой мұнарасында дискілерді үсті-үстіне жинауға болатын $A$, $B$ және $C$ атты үш баған бар. Дискілерді әртүрлі бағандар арасында жылжытуға болады, бірақ келесі ережелерді сақтау қажет:

• Бір жүрісте тек бір дискіні ғана жылжытуға болады;
• Әр жүрісте тек бір бағанның ең үстіндегі дискіні екінші бағанның ең үстіне жылжытуға болады;
• $B$ және $C$ бағандарында ешбір дискіні өзінен кіші дискінің үстіне қоюға болмайды;
• $A$ бағанында үлкенірек дискілерді кішірек дискілердің үстіне қоюға болады.

Бастапқыда Jelefy өлшемдері әртүрлі $n$ дискіні $A$ бағанына кездейсоқ ретпен жинап қояды да, $B$ мен $C$ бағандарын бос қалдырады. Жоғарыдағы шарттар орындалғанда, Jelefy барлық дискілерді $A$ бағанынан $B$ бағанына көшіру үшін қанша жүріс қажет екенін білгісі келеді.

Кіріс деректер

Бірінші жолда тесттер санын білдіретін бір бүтін сан $T$ ($1\leq T\leq 10^4$) берілген.

Әрбір тест үшін: Бірінші жолда бастапқы күйдегі $A$ бағанындағы дискілер санын білдіретін бір бүтін сан $n$ ($1\leq n\leq 10^5$) берілген.

Екінші жолда $n$ бүтін сан $p_1,p_2,\ldots,p_n$ ($1\leq p_i\leq n$) берілген, мұндағы $p_i$ — $A$ бағанындағы төменнен жоғары қарай санағандағы $i$-ші дискінің диаметрі. $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$