길이가 $n$인 정수 수열 $a_1, a_2, \dots, a_n$이 주어집니다. 다음 연산을 정확히 한 번 수행할 수 있습니다:

• $1, 2, \dots, n$의 순열 $p_1, p_2, \dots, p_n$을 하나 선택합니다.
• 그런 다음, $i$가 $1$부터 $n$까지 자연스러운 순서대로 다음을 실행합니다: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ 여기서 $a_0 = 0$이고 $a_{n+1} = 0$입니다.

목표는 연산이 완료된 후 수열의 모든 원소의 합을 최대화하는 것입니다.

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 하나의 정수 $t$ ($1 \le t \le 10^4$)가 주어집니다. 각 테스트 케이스에 대하여:

첫 번째 줄에 정수 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어집니다.

두 번째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$)이 주어집니다.

모든 테스트 케이스에서 $n$의 합은 $2 \cdot 10^5$을 초과하지 않습니다.

출력

각 테스트 케이스마다 연산을 수행한 후 수열의 모든 원소의 가능한 최대 합을 나타내는 정수를 한 줄에 출력합니다.

예제

입력

4
3
1 2 3
4
-1 3 7 6
5
4 1 0 5 2
6
4 -3 7 5 -9 3

출력

22
85
72
79