為咗慶祝喺第三屆 Universal Cup 準決賽入面冇隊伍過到「佇列編輯器」（Queue Editor）呢題，小青魚諗出咗一道關於佇列（queue）同埋……今次仲有堆疊（stack）嘅新題目！佢有 $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$。