為了慶祝在第三屆 Universal Cup 準決賽中沒有隊伍通過「佇列編輯器」（Queue Editor）一題，小青魚想出了一道關於佇列以及……這一次還有堆疊的新題目！他有 $n$ 個編號從 $1$ 到 $n$ 的球。這些球最初排列在一個佇列中，同時他還有一個空堆疊。當佇列非空時，他會執行以下步驟：

1. 移除佇列前端的球。設其編號為 $x$。
2. 當堆疊非空且堆疊頂端球的編號大於 $x$ 時，移除堆疊頂端的球並將其附加到佇列尾端。各球按其被移除的先後順序依次附加到佇列尾端。
3. 將編號為 $x$ 的球推入堆疊頂端。

可以證明，經過有限步後佇列一定會變為空。求在此之前小青魚將球推入堆疊中的總次數。

輸入格式

本題包含多組測試資料。輸入的第一行包含一個整數 $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$。