Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are playing a game in which your task is to gain as much point as possible from a 2*N grid. Each of the cell is denoted by a pair of indices \((i,j)\) that means the cell in the intersection of \(i\)-th row and \(j\)-th column and contains an integer \(Ai,j\).

Your character is standing at cell \((1,1)\) and will have to end at cell \((2,N)\). You have three options to move your character:

• move to the right cell, in other words cell \((i,j)\) to cell \((i,j+1)\)
• move to the down cell, in other words cell \((i,j)\) to cell \((i+1,j)\)
• jump any number of consecutive cells to the right that means chose some arbitary number \(x\) and jump from cell \((i,j)\) to cell \((i,j+1+x)\) , this operation will cost \((j+1)+(j+2)+(j+3)+...+(j+x)\) points. In other words if you jump over a cell \((i,j)\) it will cost you \(j\) points.

Every cell \((i,j)\) you visit the value \(Ai,j\) will be added to your score.
What is the maximum score you can achieve from the game.

Note: Your character must visit cell \((1,1)\) and cell \((2,N)\)

Input

First line of input takes an integer \(T\) : number of testcases
First line of each testcase takes an integer \(N\) : number of columns
Second and third line each takes \(N\) integers A\(i,j\) : points of the cell
\(1 \le T \le 1000\)
\(1 \le N \le 2*10^5\)
\(-10^9 \le Ai,j \le 10^9\)

sum of \(N\) over all testcase will not exceed \(2*10^5\)

Output

Output one integer in each of the \(T\) line : the maximum score you can achieve

Sample

3
4
1 1 2 3
2 -3 4 5
4
1 -3 2 4
1 1 1 5
3
1 1 1
1 1 -10

13
10
-7

testcase 1:
One of the optimal way is:
visit cell (1,1) score = 1
visit cell (1,2) score = 1+1 = 2
visit cell (1,3) score = 2+2 = 4
visit cell (2,3) score = 4+4 = 8
visit cell (2,4) score = 8+5 = 13

testcase 2:
one of the optimal way is:
visit cell (1,1) score = 1
jump cell (1,2) score = 1-2 = -1
visit cell (1,3) score = -1+2 = 1
visit cell (1,4) score = 1+4 = 5
visit cell (2,4) score = 5+5 = 10

testcase 3:
without jumping over any cell any of the valid path will give the same answer -7