Windblume Festival

The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationships people have. Source: Genshin Impact Official. During the festival, a famous game is played every year, invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, $n$ players numbered from $1$ to $n$ stand in a circle, each holding an integer. Each turn, one player is removed. The game ends when only one player is left. For each turn, let $k$ be the number of players remaining and $a\_i$ be the integer player $i$ holds. Two adjacent players, $x$ and $(x \bmod k + 1)$, are selected, and player $(x \bmod k + 1)$ is removed from the game. Player $x$'s integer then changes from $a\_x$ to $(a\_x - a\_{x \bmod k + 1})$. Player $y$ in this turn becomes player $(y - 1)$ in the next turn for all $x < y \le k$, though the integer they hold does not change. Jean wants to know the maximum possible integer held by the last remaining player by selecting the players in each round optimally.

There are multiple test cases. The first line of the input contains one integer $T$, the number of test cases. For each test case: The first line contains one integer $n$ ($1 \le n \le 10^6$), the initial number of players. The next line contains $n$ integers $a\_i$ ($-10^9 \le a\_i \le 10^9$), where $a\_i$ is the integer held by player $i$ at the beginning. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, output one line containing one integer, the maximum possible integer.

For the first sample test case, follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn. $\{\underline{1}, -3, 2, \underline{-4}\}$ (select $x = 4$) $\to$ $\{-3, \underline{2, -5}\}$ (select $x = 2$) $\to$ $\{\underline{-3, 7}\}$ (select $x = 2$) $\to$ $\{10\}$.