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$