세 명의 탐정

치탄다(Chitanda)는 $n$개의 정수로 이루어진 수열 $a_1, a_2, \ldots, a_n$을 가지고 있다. 그녀는 스카이워커트(Skywalkert)와 게임을 하려고 한다.

먼저 치탄다가 매개변수 $k$를 고르고 $a_{k+1}, a_{k+2}, \ldots, a_n$을 제거한다. 그러면 수열 $a$에는 정확히 $k$개의 정수가 남는다.

그다음 스카이워커트는 $a$의 부분수열을 골라 $a$에서 제거할 수 있다. 그가 고른 부분수열이 $a_{p_1}, a_{p_2}, \ldots, a_{p_m}$이라면, 반드시 $p_1 < p_2 < \ldots < p_m$이고 $a_{p_1} \le a_{p_2} \le \ldots \le a_{p_m}$이어야 한다.

스카이워커트는 이 연산을 최대 5번까지 할 수 있다. 그의 점수는 이 연산들에서 고른 모든 정수의 합이다.

치탄다가 고를 수 있는 각 매개변수 $k$에 대해, 스카이워커트가 얻을 수 있는 최대 점수를 구하라.

첫 번째 줄에 테스트 케이스의 개수 $T$($1 \le T \le 10000$)가 주어진다.

각 테스트 케이스의 첫 줄에는 수열의 길이 $n$($1 \le n \le 100000$)이 주어진다. 둘째 줄에는 수열의 원소 $a_1, a_2, \ldots, a_n$($1 \le a_i \le 10^9$)이 주어진다.

모든 테스트 케이스의 $n$을 합하면 500000 이하이다.

각 테스트 케이스마다 $s_1, s_2, \ldots, s_n$을 공백으로 구분하여 한 줄에 출력한다. $s_i$는 $k = i$일 때 스카이워커트가 얻을 수 있는 최대 점수이다.