Multi-Heads Cup, atau disingkat MHC, adalah kontes pemrograman seluruh dunia yang dibuat untuk para peserta dengan banyak sekali kepala. Pada tahun 2023, ketua juri acara ini, Little Cyan Fish, memecahkan masalah autentikasi yang rumit menggunakan banyak jenis tanda kurung.

Itu adalah pertama kalinya Little Cyan Fish melihat kontestan dengan banyak sekali kepala. Dan kali ini, Little Cyan Fish membawa masalah tanda kurung lainnya kepada sahabatnya yang memiliki banyak sekali kepala. Little Cyan Fish memiliki $n$ jenis tanda kurung di tangannya, dan setiap jenis tanda kurung dibagi menjadi kurung buka dan kurung tutup. Untuk memudahkan, kita menggunakan $L^i$ untuk menyatakan kurung buka jenis ke-$i$, dan $R^i$ untuk menyatakan kurung tutup jenis ke-$i$.

"Hei, jangan lupa," pikir Little Cyan Fish, "Aku sudah pernah memperkenalkan kepadamu apa itu barisan kurung seimbang sebelumnya!" Untuk memastikan Anda memahami konsep barisan kurung seimbang, Little Cyan Fish menyiapkan definisi formal berikut tentang barisan kurung seimbang:

• $\varepsilon$ (string kosong) adalah barisan kurung seimbang.
• Jika $A$ adalah barisan kurung seimbang, $(A)$ juga merupakan barisan kurung seimbang.
• Jika $A$ dan $B$ adalah barisan kurung seimbang, maka $AB$ juga merupakan barisan kurung seimbang.

Sebagai contoh, "()", "()()", dan "(())" adalah barisan kurung seimbang, tetapi ")(", "(", dan "))" bukan.

Sekarang, Little Cyan Fish memberi Anda sebuah barisan kurung $S$ dengan panjang $n$, yang berisi $n$ jenis tanda kurung. Sayangnya, Little Cyan Fish melupakan jenis tanda kurung di beberapa posisi, dan juga melupakan arah tanda kurung di posisi-posisi tersebut. Ingatan tentang posisi-posisi ini telah menjadi kabur dan direpresentasikan dengan ? oleh Little Cyan Fish.

Little Cyan Fish sangat penasaran, untuk semua $1 \le l \le r \le n$, berapa banyak pasangan $(l, r)$ yang bersesuaian dengan substring $S[l \dots r]$, sedemikian sehingga terdapat cara untuk mengisi ? dengan suatu jenis tanda kurung dalam suatu arah, sehingga untuk setiap $1 \le i \le n$, berlaku:

• Ekstrak semua tanda kurung jenis $i$ (yaitu semua $L^i$ dan $R^i$), barisan kurung yang dihasilkan (hanya berisi tanda kurung jenis ke-$i$) adalah barisan kurung seimbang.

Sebagai contoh, jika kita menggunakan "()" untuk menyatakan tanda kurung jenis pertama dan "[]" untuk menyatakan tanda kurung jenis kedua, string kurung ([?) memenuhi kondisi di atas, karena kita dapat mengganti ? dengan ]. (?)] juga memenuhi kondisi di atas, karena kita dapat mengganti ? dengan [.

Little Cyan Fish ingin Anda menghitung banyaknya semua pasangan $(l, r)$ yang valid.

Masukan

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

Untuk setiap kasus uji, baris pertama dari masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 2 \times 10^5$), yang menyatakan panjang string kurung.

Baris berikutnya berisi $n$ bilangan bulat $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). $n$ bilangan bulat ini menjelaskan informasi string kurung, di mana:

• Jika $x_i > 0$, maka posisi ke-$i$ merepresentasikan kurung buka jenis ke-$x_i$ (yaitu $L^{x_i}$).
• Jika $x_i < 0$, maka posisi ke-$i$ merepresentasikan kurung tutup jenis ke-$-x_i$ (yaitu $R^{-x_i}$).
• Jika $x_i = 0$, itu berarti Little Cyan Fish melupakan informasi pada posisi ini (yaitu ?).

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

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi satu bilangan bulat, yang menyatakan jawabannya.

Contoh

Masukan 1

4
4
1 2 -1 -2
4
1 0 -2 0
6
1 2 3 -3 -2 -1
8
1 0 0 3 0 0 0 -2

Keluaran 1

1
3
3
14