题目描述

小卉刚刚学习了子序列的定义。如果$b$可以通过$a$删除零个或者多个元素而不改变剩余元素的顺序得到，则序列$b$是$a$的子序列。例如：如果$a=[1,2,3,4,5,1,2]$，则可能的子序列为：$[1,2,3],[1]$和$[1,2,3,4,5,1,2]$, 但是$[1,1,3]$不是$a$的子序列。

现在小卉想知道给定一个由正数和负数组成的序列$a$(序列中没有零)，那么序列$a$的最长的交叉子序列中元素和最大的是多少。交叉子序列，指的是子序列中每下一个元素的符号与当前元素的符号相反，如正、负、正或者负、正、负等。

换句话说，小卉想请你找到最长的交叉子序列中元素和最大的那个，然后输出最大的元素和。

输入

第一行包含一个整数$t(1\leq t\leq 10^4)$，样例的数量。 接下来的$t$个样例中 第一行包含一个整数$n(1\leq n\leq 2\times 10^5)$，表示序列a中元素的数量。 第二行包含$n$个整数$a_1,a_2,a_3……a_n$$(-10^9\leq a_i\leq 10^9,a_i$不等于0) 保证每个样例中$n$的总和不超过$2\times 10^5$.

输出

对于每一个样例，输出答案：最长交叉子序列的元素和。

Samples

4  
5  
1 2 3 -1 -2  
4  
-1 -2 -1 -3  
10  
-2 8 3 8 -4 -15 5 -2 -3 1  
6  
1 -1000000000 1 -1000000000 1 -1000000000

2  
-1  
6  
-2999999997