题目描述

$n$ 名编号为 $1$ 到 $n$ 的玩家围成一圈，每人持有一个整数。每轮会移除一名玩家，游戏只剩一名玩家时结束。

每轮：

• 设当前剩余玩家数为 $k$，玩家 $i$ 所持整数为 $a_i$；
• 选择相邻的两名玩家 $x$ 与 $(x \bmod k) + 1$ ，$(1 \le x \le k)$；
• 玩家 $x$ 的整数变为 $a_x - a_{(x \bmod k) + 1}$；
• 移除玩家 $(x \bmod k )+ 1$；
• 这一轮对于所有编号为($x < y \le k$) $y$ 的玩家在下一轮变为编号 $y-1$（所持整数不变）。

通过每轮最优地选择玩家，最后剩下的玩家所持整数的最大可能值是多少。

输入格式

• 第一行一个整数 $T$，表示测试用例数量。
• 每个测试用例：
  • 第一行一个整数 $n\ (1 \le n \le 10^6)$，表示初始玩家数；
  • 第二行 $n$ 个整数 $a_i\ (-10^9 \le a_i \le 10^9)$，表示玩家初始所持整数。

所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

每个测试用例输出一行一个整数，表示最后剩下的玩家所持整数的最大可能值。

样例

5
4
1 -3 2 -4
11
91 66 73 71 32 83 72 79 84 33 93
12
91 66 73 71 32 83 72 79 84 33 33 93
13
91 66 73 71 32 83 72 79 84 33 33 33 93
1
0

10
713
746
779
0