该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师有一个数组，其中有正有负，他可以无数次选择任意数量的数字删除，现在请你计算最后数组的和的最大值是多少

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数

对于每组测试，第一行一个正整数$n(1 \leq n \leq 10^5)$，表示数组长度

第二行n给整数$a_i(-10^9 \leq a_i \leq 10^9)$，表示数组元素大小

Output

输出一个整数，表示操作完成后数组最大和

Samples

1
5
1 2 3 4 5

15

Limitation

1s, 1024KiB for each test case.