sgg 的团建游戏II
说明
传炸弹游戏实在是太烧脑了，而且相当破坏感情于是老师决定带领同学们玩一玩简单的游戏——二十四点
但是二十四点实在是太没意思了，同学们相当无聊
于是 sgg 在二十四点的基础上进行了一些改动
现在 sgg 请老师随机的写出一个加减法式子
同学们可以在这个式子的任意位置添加括号（数字或者符号两侧均可添加）
最后只要式子合法即可，这里我们认为 $(1+2)-(4-5)$ 这样的式子是合法的，但是$1+)2，1(-)2$ 这样是不合法的
现在 sgg 想知道，对于一个式子，最大结果是多少？
输入格式
输入第一行包含一个整数 $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 - 997
110
相关
在下列比赛中: