Sum
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Problem Number: 
有一个数列 。
你每次可以选择任意 个数，这 k 个数的和 S 会成为你这次操作的得分。操作结束后，你要把这 k 个数删除，然后在数组中加入 S。
操作数可以为 0，求最大得分。

输入描述:

本题多测。
第一行一个整数 T，表示数据组数。
对于每组数据：
- 第一行一个数 n，表示数列长度。
- 接下来一行 n 个数 a_i，表示这个数列 。

输出描述:

对于每组数据，仅一行一个数，即最高得分。
由于结果可能较大，你只需要输出答案对  取模的值。
示例1

输入

复制 
3
4
2 -1 1 3
3
-1 -1 3
3
-1 -2 -2022

输出

复制 
16
3
0

说明

样例 1 说明
- 第一次，选择 [\underline{\textbf{2}},-1,1,\underline{\textbf{3}}]，S=5，数列变为 [-1,1,5]。
- 第二次，选择 [-1,\underline{\textbf{1}},\underline{\textbf{5}}]，S=6，数列变为 [-1,6]。
- 第三次，选择 [\underline{\textbf{-1}},\underline{\textbf{6}}]，S=5。
- 结束游戏。
总得分 5+6+5=16。

样例 3 说明
不作操作，得分 0。

备注:

对于  的数据，都有 ，，。

令  表示单个测试点内所有 n 的和，则 。