Để ăn mừng việc không có đội nào giải được bài toán "Queue Editor" tại Bán kết The 3rd Universal Cup, Little Cyan Fish đã nghĩ ra một bài toán mới liên quan đến một hàng đợi và... lần này là cả một ngăn xếp! Cậu có $n$ quả bóng được đánh số từ $1$ đến $n$. Ban đầu các quả bóng được sắp xếp trong một hàng đợi, và cậu cũng có một ngăn xếp rỗng. Trong khi hàng đợi chưa rỗng, cậu thực hiện các bước sau:

1. Lấy quả bóng ở đầu hàng đợi ra. Gọi $x$ là nhãn của nó.
2. Trong khi ngăn xếp chưa rỗng và nhãn của quả bóng ở đỉnh ngăn xếp lớn hơn $x$, lấy quả bóng ở đỉnh ngăn xếp ra và thêm nó vào cuối hàng đợi. Các quả bóng được thêm vào cuối hàng đợi theo đúng thứ tự chúng bị lấy ra.
3. Đẩy quả bóng có nhãn $x$ vào đỉnh ngăn xếp.

Có thể chứng minh rằng hàng đợi sẽ trở nên rỗng sau hữu hạn bước. Hãy tìm tổng số lần Little Cyan Fish đẩy một quả bóng vào ngăn xếp trước khi điều này xảy ra.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 5 \times 10^5$), cho biết số lượng quả bóng. Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), cho biết nhãn của các quả bóng trong hàng đợi ban đầu từ đầu đến cuối. Dữ liệu đảm bảo rằng $a_1, a_2, \ldots, a_n$ tạo thành một hoán vị của $1, 2, \ldots, n$.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $5 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên duy nhất, cho biết tổng số lần một quả bóng được đẩy vào ngăn xếp.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
3
5
4

Dữ liệu vào 2

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

Dữ liệu ra 2

6
15

Ghi chú

Trong ví dụ đầu tiên, dãy các nhãn được đẩy vào ngăn xếp lần lượt là $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ và $(3, 1, 2, 3)$ trong bốn bộ dữ liệu. Hình vẽ trong đề bài minh họa bộ dữ liệu thứ ba trong ví dụ đầu tiên.

Trong bộ dữ liệu đầu tiên của ví dụ thứ hai, dãy các nhãn được đẩy vào là $(2, 3, 1, 3, 2, 3)$, vì vậy đáp án là $6$. Trong bộ dữ liệu thứ hai của ví dụ thứ hai, dãy đó là $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, vì vậy đáp án là $15$.