The 3rd Universal Cup Semifinals において問題「Queue Editor」を解いたチームがいなかったことを祝して、Little Cyan Fish はキューと……今回はさらにスタックを使った新しい問題を考案しました！彼は $n$ 個のボールを持っており、それぞれ $1$ から $n$ までの番号が付けられています。最初、ボールはキューに並んでおり、さらに彼は空のスタックも持っています。キューが空でない間、彼は以下の手順を繰り返します：

1. キューの先頭にあるボールを取り除く。その番号を $x$ とする。
2. スタックが空でなく、かつスタックの一番上にあるボールの番号が $x$ より大きい間、スタックの一番上のボールを取り除き、キューの末尾に追加する。ボールは取り除かれた順番にキューへ追加される。
3. 番号 $x$ のボールをスタックの一番上に積む（プッシュする）。

有限回のステップの後にキューが空になることが示せます。そうなるまでに Little Cyan Fish がボールをスタックに積む合計回数を求めてください。

入力

入力は複数のテストケースからなる。入力の最初の行には、テストケースの個数を表す単一の整数 $T$（$1 \le T$）が与えられる。

各テストケースについて、最初の行にはボールの個数を表す単一の整数 $n$（$1 \le n \le 5 \times 10^5$）が与えられる。2 行目には $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 行に出力せよ。

入出力例

入力 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 つ目の例では、4 つのテストケースにおいてスタックに積まれるボールの番号の列はそれぞれ $(1)$、$(1, 2, 3)$、$(2, 1, 3, 2, 3)$、$(3, 1, 2, 3)$ です。問題文中の図は、1 つ目の例の 3 番目のテストケースを示しています。

2 つ目の例の 1 番目のテストケースでは、スタックに積まれる番号の列は $(2, 3, 1, 3, 2, 3)$ であるため、答えは $6$ です。2 つ目の例の 2 番目のテストケースでは、列は $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$ であるため、答えは $15$ です。