Description

蒙德城的风花节即将到来！人们正在为巴巴托斯和他们所爱的人准备风花。风花节也是一个改善人际关系的机会。

在节日期间，每年都会玩一个由代理团长琴发明的著名游戏。在游戏中，编号从 $1$ 到 $n$ 的 $n$ 个玩家围成一个圈，每人手中持有一个整数。每一轮，将有一名玩家被移除。游戏将在只剩下一名玩家时结束。

在每一轮中，设 $k$ 为剩余玩家的数量，$a_i$ 为玩家 $i$ 手中的整数。选择两个相邻的玩家 $x$ 和 $(x \bmod k + 1)$，并将玩家 $(x \bmod k + 1)$ 移出游戏。然后玩家 $x$ 的整数将从 $a_x$ 变为 $(a_x - a_{x \bmod k + 1})$。在本轮中，玩家 $y$ 在下一轮中将成为玩家 $(y - 1)$，对于所有 $x < y \le k$，尽管他们手中的整数不会改变。

琴想知道通过在每轮中最优地选择玩家，最后剩下的玩家手中可能持有的最大整数。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示初始的玩家数量。

下一行包含 $n$ 个整数 $a_i$ ($-10^9 \le a_i \le 10^9$)，其中 $a_i$ 是玩家 $i$ 在开始时持有的整数。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

Output Format

对于每个测试用例，输出一行，包含一个整数，表示可能的最大整数。

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

Hint

对于第一个样例测试用例，遵循如下策略，其中下划线的整数是每轮中被选中的玩家持有的整数。

$\{\underline{1}, -3, 2, \underline{-4}\}$（选择 $x = 4$）$\to$ $\{-3, \underline{2, -5}\}$（选择 $x = 2$）$\to$ $\{\underline{-3, 7}\}$（选择 $x = 2$）$\to$ $\{10\}$。

题面翻译由 ChatGPT-4o 提供。