바람꽃 축제

몬드시티에서 바람꽃 축제가 곧 열린다! 사람들은 바르바토스와 사랑하고 아끼는 사람들을 위해 바람꽃을 준비하고 있다. 바람꽃 축제는 사람들 사이의 관계를 개선하는 기회이기도 하다. 출처: Genshin Impact Official. 축제 기간마다 서풍 기사단의 대단장 대리 Jean이 고안한 유명한 게임이 열린다. 게임에서는 1번부터 $n$번까지 번호가 매겨진 $n$명의 플레이어가 원형으로 서 있고, 각자 정수 하나씩을 들고 있다. 매 턴마다 플레이어 한 명이 제거된다. 플레이어가 한 명만 남으면 게임이 끝난다. 각 턴에서 남은 플레이어 수를 $k$, 플레이어 $i$가 들고 있는 정수를 $a\_i$라고 하자. 서로 인접한 두 플레이어 $x$와 $(x \bmod k + 1)$을 고르고, 플레이어 $(x \bmod k + 1)$을 게임에서 제거한다. 그러면 플레이어 $x$가 들고 있는 정수는 $a\_x$에서 $(a\_x - a\_{x \bmod k + 1})$로 바뀐다. 이 턴에서 플레이어 $y$는 $x < y \le k$인 모든 $y$에 대해 다음 턴에 플레이어 $(y - 1)$이 되지만, 들고 있는 정수는 바뀌지 않는다. Jean은 매 라운드마다 플레이어를 최적으로 골라, 마지막에 남는 플레이어가 가질 수 있는 정수의 최댓값을 알고 싶어 한다.

입력에는 여러 개의 테스트 케이스가 있다. 첫 줄에 테스트 케이스의 수 $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$을 넘지 않는다고 보장된다.

각 테스트 케이스마다 한 줄에 가능한 정수의 최댓값을 출력한다.

첫 번째 샘플 테스트 케이스는 아래 전략을 따른다. 밑줄 친 정수는 각 턴에서 선택된 플레이어가 들고 있는 정수이다. $\{\underline{1}, -3, 2, \underline{-4}\}$ ($x = 4$ 선택) $\to$ $\{-3, \underline{2, -5}\}$ ($x = 2$ 선택) $\to$ $\{\underline{-3, 7}\}$ ($x = 2$ 선택) $\to$ $\{10\}$.