Linh nhỏ đang sắp xếp một hàng gồm ~n~ tủ trưng bày cho một triển lãm đá quý. Tủ thứ ~i~ trưng bày một viên đá quý được gắn nhãn bằng một số nguyên không âm ~a_i~, hoặc là để trống — các tủ trống được ký hiệu bởi ~a_i = -1~. Với mỗi tủ trống, Linh có thể đặt vào đó một viên đá quý với bất kỳ nhãn số nguyên không âm nào mà cô ấy chọn.

Gọi ~\mathrm{MaxMex}(l, r)~ của đoạn ~a_l, a_{l + 1}, \ldots, a_r~ là mex^∗ lớn nhất có thể đạt được của các nhãn đá quý bằng cách đặt các viên đá quý có nhãn không âm vào tất cả các tủ trống bên trong đoạn đó.

Hãy giúp Linh tính ~\displaystyle\sum_{1 \le l \le r \le n} \mathrm{MaxMex}(l, r)~.

Lưu ý rằng ~\mathrm{MaxMex}~ của các đoạn được tính độc lập với nhau. Tức là, nếu hai đoạn cùng chứa một tủ trống, Linh có thể chọn một viên đá cho tủ đó để tối đa hóa ~\mathrm{MaxMex}~ của một đoạn, và chọn một viên đá khác cho cùng tủ đó để tối đa hóa ~\mathrm{MaxMex}~ của đoạn còn lại.

∗ mex của một đa tập là số nguyên không âm nhỏ nhất không xuất hiện trong nó; ví dụ, ~\mathrm{mex}(\{0, 1, 1, 3\}) = 2~ và ~\mathrm{mex}(\{1, 2\}) = 0~.

Input

Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 5000~) — số lượng tủ trưng bày.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~a_i = -1~ hoặc ~0 \le a_i \le 10^9~) – nhãn của các viên đá trong tủ, với tủ trống có ~a_i = -1~.

Output

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất — tổng ~\displaystyle\sum_{1 \le l \le r \le n} \mathrm{MaxMex}(l, r)~.

Scoring

Sample Input 1

3
3
0 2 -1
5
1 -1 3 -1 5
4
0 1 2 3

Sample Output 1

7
22
10

Notes

Trong test case đầu tiên, ~a = [0, 2, -1]~, với tủ thứ ba là tủ trống. Dưới đây mã giá trị ~\mathrm{MaxMex}~ của các đoạn chứa tủ thứ ~3~:

• ~\mathrm{MaxMex}(1, 3) = 3~. Đặt vào tủ 3 viên đá có nhãn ~1~, thu được ~\mathrm{mex}(\{0, 2, 1\}) = 3~.

• ~\mathrm{MaxMex}(2, 3) = 1~. Đặt vào tủ 3 viên đá có nhãn ~0~, thu được ~\mathrm{mex}(\{2, 0\}) = 1~.

• ~\mathrm{MaxMex}(3, 3) = 1~. Đặt vào tủ 3 viên đá có nhãn ~0~, thu được ~\mathrm{mex}(\{0\}) = 1~.

Kết quả thu được là:

$$\begin{array}{llllll} \displaystyle\sum_{1 \le l \le r \le n} \mathrm{MaxMex}(l, r) \\ = \mathrm{MaxMex}(1, 1) & + \mathrm{MaxMex}(1, 2) & + \mathrm{MaxMex}(1, 3) & + \mathrm{MaxMex}(2, 2) & + \mathrm{MaxMex}(2, 3) & + \mathrm{MaxMex}(3, 3) \\ = 1 & + 1 & + 3 & + 0 & + 1 & + 1 \\ = 7 \end{array}$$