제3회 Universal Cup 준결승에서 "Queue Editor" 문제를 해결한 팀이 단 한 팀도 없었다는 사실을 기념하기 위해, Little Cyan Fish는 큐와... 이번에는 스택까지 포함된 새로운 문제를 생각해 냈습니다! 그에게는 $1$부터 $n$까지 번호가 매겨진 $n$개의 공이 있습니다. 공들은 처음에 큐에 배열되어 있으며, 비어 있는 스택도 하나 가지고 있습니다. 큐가 비어 있지 않은 동안, 그는 다음 단계를 수행합니다:

1. 큐의 맨 앞에 있는 공을 제거합니다. 그 공의 번호를 $x$라고 합시다.
2. 스택이 비어 있지 않고 스택의 맨 위에 있는 공의 번호가 $x$보다 큰 동안, 스택의 맨 위에서 공을 제거하여 큐의 맨 뒤에 추가합니다. 공들은 제거된 순서대로 추가됩니다.
3. 번호가 $x$인 공을 스택의 맨 위에 넣습니다(push).

유한 번의 단계를 거치면 큐가 비게 됨을 보일 수 있습니다. 큐가 비게 되기 전까지 Little Cyan Fish가 공을 스택에 넣는 총횟수를 구하세요.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T$)가 하나 주어집니다.

각 테스트 케이스에 대해, 첫 번째 줄에는 공의 개수를 나타내는 정수 $n$ ($1 \le n \le 5 \times 10^5$)이 하나 주어집니다. 두 번째 줄에는 초기 큐의 맨 앞부터 맨 뒤까지 있는 공들의 번호를 나타내는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)이 주어집니다. $a_1, a_2, \ldots, a_n$은 $1, 2, \ldots, n$의 순열임이 보장됩니다.

모든 테스트 케이스에 대한 $n$의 합은 $5 \times 10^5$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 한 줄에 하나의 정수로 공이 스택에 들어간 총횟수를 출력합니다.

예제

입력 1

4
1
1
3
1 2 3
3
2 1 3
3
3 1 2

출력 1

1
3
5
4

입력 2

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

출력 2

6
15

참고

첫 번째 예제에서 네 개의 테스트 케이스 동안 스택에 들어간 공의 번호 수열은 각각 $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$, $(3, 1, 2, 3)$입니다. 문제 설명의 그림은 첫 번째 예제의 세 번째 테스트 케이스를 보여줍니다.

두 번째 예제의 첫 번째 테스트 케이스에서 스택에 들어간 번호 수열은 $(2, 3, 1, 3, 2, 3)$이므로 답은 $6$입니다. 두 번째 예제의 두 번째 테스트 케이스에서 수열은 $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$이므로 답은 $15$입니다.