蒙德城的风花节就要到了！人们正在为巴巴托斯以及他们所爱和崇拜的人准备风之花。风花节也是一个改善人际关系的好机会。

来源：原神官方

节日期间，每年都会进行一场由西风骑士团代理团长琴发明的著名游戏。在游戏中，有 $n$ 名编号从 $1$ 到 $n$ 的玩家围成一个圆圈，每人手中持有一个整数。每一轮，会有一名玩家被淘汰。当只剩下一名玩家时，游戏结束。

在每一轮中，设 $k$ 为剩余玩家的数量，$a_i$ 为玩家 $i$ 持有的整数。选择两名相邻的玩家 $x$ 和 $(x \pmod k + 1)$，玩家 $(x \pmod k + 1)$ 将被淘汰。玩家 $x$ 持有的整数将变为 $(a_x - a_{x \pmod 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$)，其中 $a_i$ 是玩家 $i$ 最初持有的整数。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

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

样例

输入 1

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

输出 1

10
713
746
779
0

说明

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

$\{1, -3, 2, -4\}$ (选择 $x = 4$) $\to \{-3, 2, -5\}$ (选择 $x = 2$) $\to \{-3, 7\}$ (选择 $x = 2$) $\to \{10\}$。