hyk 的团建游戏II

传炸弹游戏实在是太烧脑了，而且相当破坏感情

于是老师决定带领同学们玩一玩简单的游戏——二十四点

但是二十四点实在是太没意思了，同学们相当无聊

于是 hyk 在二十四点的基础上进行了一些改动

现在 hyk 请老师随机的写出一个加减法式子

同学们可以在这个式子的任意一个位置添加括号（数字或者符号两侧均可添加）

最后只要式子合法即可，这里我们认为 $(1+2)-(4-5)$ 这样的式子是合法的，但是 $1+)2，1(-)2$ 这样是不合法的

现在 hyk 想知道，对于一个式子，最大结果是多少？

输入第一行包含一个整数 $T$ ，表示有 $T$ 次游戏

对于每次游戏：

输入的第一行包含一个正整数 $n$ 表示数字的个数

接下来一行一共 $2n-1$ 个符号或者非负整数，组成一个由空格隔开的式子

一个整数，表示添加括号以后可以得到的最大结果

对于 $10\%$ 的数据满足: $n \leq 3$

对于另外 $20\%$ 的数据满足: $n \leq 10, T \leq 10$

对于另外 $20\%$ 的数据满足: $n \leq 100, T \leq 100$

对于另外 $20\%$ 的数据满足: $n \leq 1000, T \leq 100$

对于 $100\%$ 的数据满足: $n \leq 10^5, \sum{n} \leq 2 * 10^5, 2 \leq n$

特别的，保证输入的所有非负整数均在区间 $[0,10^9]$ 内

2
3
5 - 1 - 3
6
10 - 3 + 9 - 4 + 9 - 99

7
110

#7166. hyk 的团建游戏II