Untuk merayakan fakta bahwa tidak ada tim yang berhasil menyelesaikan soal "Queue Editor" pada Semifinal The 3rd Universal Cup, Little Cyan Fish telah membuat sebuah soal baru yang melibatkan antrean (queue) dan... kali ini, sebuah tumpukan (stack)! Ia memiliki $n$ bola yang diberi label dari $1$ hingga $n$. Bola-bola tersebut awalnya disusun di dalam sebuah antrean, dan ia juga memiliki sebuah tumpukan kosong. Selama antrean tidak kosong, ia melakukan langkah-langkah berikut:

1. Keluarkan bola yang berada di bagian depan antrean. Misalkan $x$ adalah labelnya.
2. Selama tumpukan tidak kosong dan label bola paling atas pada tumpukan lebih besar dari $x$, keluarkan bola paling atas dari tumpukan dan tambahkan ke bagian belakang antrean. Bola-bola tersebut ditambahkan sesuai dengan urutan saat mereka dikeluarkan.
3. Masukkan (push) bola berlabel $x$ ke bagian atas tumpukan.

Dapat dibuktikan bahwa antrean akan menjadi kosong setelah sejumlah langkah berhingga. Carilah total berapa kali Little Cyan Fish memasukkan bola ke dalam tumpukan sebelum hal ini terjadi.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 5 \times 10^5$), yang menyatakan banyaknya bola. Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), yang menyatakan label bola-bola di dalam antrean awal dari depan ke belakang. Dijamin bahwa $a_1, a_2, \ldots, a_n$ membentuk sebuah permutasi dari $1, 2, \ldots, n$.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $5 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat, yang menyatakan total berapa kali sebuah bola dimasukkan ke dalam tumpukan.

Contoh

Masukan 1

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

Keluaran 1

1
3
5
4

Masukan 2

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

Keluaran 2

6
15

Catatan

Pada contoh pertama, barisan label yang dimasukkan ke dalam tumpukan masing-masing adalah $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$, dan $(3, 1, 2, 3)$ pada keempat kasus uji. Gambar pada deskripsi soal mengilustrasikan kasus uji ketiga pada contoh pertama.

Pada kasus uji pertama dari contoh kedua, barisan label yang dimasukkan adalah $(2, 3, 1, 3, 2, 3)$, sehingga jawabannya adalah $6$. Pada kasus uji kedua dari contoh kedua, barisannya adalah $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, sehingga jawabannya adalah $15$.