题目描述

Eralim作为黑手党首领，管理着一组n名战士。战士i的评分为ai。

Eralim安排了一场n−1场战斗的锦标赛，在每场战斗中，选择两名尚未被淘汰的战士i和j（1≤i<j≤n），战斗结果是战士i被淘汰，战士j的评分减少战士i的评分。也就是说，aj减少ai。注意，战士j的评分可能会变为负数。战士的索引不变。

Eralim想知道，如果他以最佳方式选择战斗，最后剩下的战士能保留的最大评分是多少。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量t（1≤t≤104）。接下来的描述是测试用例的内容。

每个测试用例的第一行包含一个整数n（2≤n≤2⋅105）——战士的数量。

每个测试用例的第二行包含n个整数a1,a2,…an（1≤ai≤109）——战士的评分。

所有测试用例中n的总和不超过2⋅105。

输出

对于每个测试用例，输出一个整数——最后剩下的战士能保留的最大评分。

样例

输入样例

5
2
2 1
3
2 2 8
4
1 2 4 3
5
1 2 3 4 5
5
3 2 4 5 4

输出样例

-1
8
2
7
8