Sau khi tìm ra được các tín hiệu, nhận lệnh từ cấp trên, chỉ huy Gabriel Lorca của tàu USS Discovery muốn đưa tàu đến đó để tìm hiểu thêm về các tín hiệu. Sự di chuyển trong mạng lưới bào tử sợi nấm được đảm nhiệm bởi 1 thứ gọi là Động cơ bào tử, động cơ bào tử cần sử dụng trung gian là 1 con Tardigrade để làm hoa tiêu dẫn đường trong mạng lưới sợi nấm.

Nhưng năng lượng tác động lên sinh vật đó sau mỗi lần nhảy quá lớn nên chỉ trong vài lần sau đó, con Tardigrade duy nhất đã rơi vào trạng thái ẩn sinh tột độ bằng cách giảm lượng nước trong cơ thể xuống dưới 1%. Đang trong thời chiến và loài Tardigrade cũng đang trong nguy cơ tuyệt chủng, họ không thể làm gì khác ngoài việc cố gắng hồi sức cho nó. Trong tình thế gấp gáp, 1 ý tưởng táo bạo nhưng không kém phần xuất sắc đó là hợp nhất DNA của Tardigrade vào cơ thể trung úy Paul Stamets (là người khám phá ra động cơ bào từ). Dù thử nghiệm thành công nhưng với số hành tinh cần kiểm tra quá lớn dẫn đến số lần nhảy có thể rất nhiều. Paul Stamets muốn biết được ngưỡng năng lượng lớn nhất qua hàng loạt các cú nhảy để có biện pháp phòng ngừa kịp thời. Năng lượng qua các lần nhảy sẽ biến động tuần hoàn theo chu kì mà trung úy Paul sẽ cung cấp cho các bạn ngay bên dưới. Các bạn hãy giúp anh ấy nhé!

-Yêu cầu

Các hành tinh được xem như 1 dãy số. Năng lượng cần để nhảy đến hành tinh ~i~ là ~a[i]~. Paul sẽ thực hiện 1 số lần nhảy bất kì ~(\geq1)~ và năng lượng qua các lần nhảy như sau: VD: số lần nhảy là ~k~ ~(i_1 < i_2 < … < i_k)~ thì năng lượng tổng: ~3 \cdot a[i_1] + 1 \cdot a[i_2] - 4 \cdot a[i_3] + 3 \cdot a[i_4] + 1 \cdot a[i_5] - 4 \cdot a[i_6] + ….. a[i_k]~

Tìm năng lượng tổng lớn nhất

INPUT

Dòng đầu tiên chứa ~T~ là số testcase ~(T \leq 10)~

+~T~ nhóm, mỗi nhóm có dạng:

+~N~ là số hành tinh ~(N \leq 10^5)~

+Tiếp theo là ~N~ số ~a[i]~ ~(-10^5 \leq a[i] \leq 10^5)~ biểu thị năng lượng khi nhảy đến hành tinh ~i~

OUTPUT

In ra ~T~ dòng, mỗi dòng là kết quả của testcase đó

Sample input 1

1
5
-7 -9 -2 8 2

Sample output 1

26

Sample input 2

1
2
-4 -3

Sample output 2

-9

*Giải thích test 1: Paul sẽ chọn ~i = 4~ và ~i = 5~, khi đó năng lượng sẽ là ~3 \cdot 8 + 1 \cdot 2 = 26~

Có thế thấy không có cách chọn nào để năng lượng lớn hơn

*Tính điểm: *

Subtask 1: ~T = 1, n \leq 20~ (25%)

Subtask 2: ~T = 10, n \leq 10^3~ (50%)

Subtask 3: Không có ràng buộc gì thêm (25%)