감시탑

가장 좋은 이동 수단이 말이었고, 도시 위로 성이 우뚝 솟아 있었으며, 공주는 아름답고 기사는 용맹했던 시절로 돌아가 봅시다. 바로 그 시대에 우리의 새 주인공 루치우시 대장이 살고 있었습니다.

루치우시 대장은 어느 왕국 도시의 안전을 책임지는 감시탑들을 관리합니다. 감시탑은 모두 $N$개이며 원형으로 배치되어 있습니다. 즉 첫 번째 감시탑은 두 번째 감시탑과 $N$번째 감시탑에 인접하고, 두 번째 감시탑은 첫 번째와 세 번째에 인접하는 식입니다.

루치우시 대장의 시대에는 아직 관청은 없었지만 관료주의는 이미 존재했습니다. 대장은 언제든 규정과 기준 준수를 살피는 왕실 감사관의 방문을 예상하고 있습니다. 감사관들은 대장이 관리하는 감시탑 중 일부를 점검하려 합니다. 대장은 자신의 감시탑 망에서 연속으로 인접한 감시탑들로 이루어진 임의의 연결된 구간 하나를 골라 점검 대상으로 삼을 수 있습니다.

루치우시 대장은 각 감시탑에 정수 하나(음수, 0, 또는 양수)를 부여했는데, 이는 해당 감시탑 방문이 감사관에게 남길 인상을 나타냅니다. 전체 점검의 평가 점수는 감사관이 방문한 감시탑들에서 받은 인상의 합입니다. 루치우시 대장이 기대할 수 있는 최대 평가 점수를 구하세요.

대장이 점검 대상으로 고른 구간은 감시탑을 적어도 하나 포함해야 하며, 극단적인 경우 모든 감시탑을 포함할 수도 있습니다.

입력의 첫 줄에는 테스트 집합의 개수를 나타내는 자연수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 각 테스트 집합이 차례로 주어집니다.

각 테스트 집합의 첫 줄에는 루치우시 대장이 관리하는 감시탑의 수를 나타내는 자연수 $N$ ($1 \le N \le 1000000$)이 주어집니다.

집합의 둘째 줄에는 각 감시탑이 감사관에게 남길 것으로 기대되는 인상을 나타내는 $N$개의 정수 $w_i$ ($-1000 \le w_i \le 1000$)가 공백으로 구분되어 주어집니다.

각 테스트마다 점검으로 얻을 수 있는 최대 평가 점수를 한 줄에 하나씩 출력하세요.