Ikan Sian Kecil sedang bermain Slay the Spire II dan memilih karakter "Silent".

Ikan Sian Kecil sekarang harus bertarung melawan seorang "Teman Bertarung" (Battle Friend). Pada awalnya, tumpukan "Racun" (Poison) milik Teman Bertarung dan level "Akseleran" (Accelerant) milik Anda keduanya bernilai $0$. Dalam $n$ giliran berikutnya, setiap giliran akan terjadi peristiwa-peristiwa berikut secara berurutan:

1. Menggunakan "Racun Mematikan" (Deadly Poison): menambah tumpukan Racun Teman Bertarung sebesar $x_i$.

2. Memilih apakah akan menggunakan "Akseleran": memilih apakah akan menambah level Akseleran Anda sebesar $1$.

3. Memicu efek Racun: misalkan level Akseleran Anda adalah $t$, ulangi peristiwa berikut sebanyak $t$ kali:

   • Misalkan tumpukan Racun Teman Bertarung adalah $x$. Jika $x > 0$, berikan kerusakan sebesar $x$ kepada Teman Bertarung dan kurangi tumpukan Racun sebesar $1$; sebaliknya, jika $x = 0$, tidak ada yang terjadi.

Perhatikan bahwa baik tumpukan Racun maupun level Akseleran akan tetap bertahan lintas giliran dan tidak menghilang.

Ikan Sian Kecil ingin memaksimalkan total kerusakan yang diberikan kepada Teman Bertarung selama $n$ giliran ini. Keluarkan nilai kerusakan maksimum tersebut.

Format Masukan

Masukan terdiri atas beberapa kasus uji. Baris pertama 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 5000$).

Baris kedua berisi $n$ bilangan bulat $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), yang menyatakan penambahan tumpukan Racun pada Teman Bertarung di setiap giliran.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $10^6$, dan jumlah $n^2$ di seluruh kasus uji tidak melebihi $10^8$.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat yang menyatakan total kerusakan maksimum yang dapat diberikan kepada Teman Bertarung di seluruh giliran.

Contoh

Contoh Masukan 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Contoh Keluaran 1

33
11
750
725