There are 2 trains A and B and N stations in a line from 1 to N in order. There is also an array P of length N-1 such that P_{i} (1≤ i < N) denotes the amount of time any train takes to go from the i-th station to the (i+1)-th station. 

Initially, both trains are at station 1. Train A departs from station 1 and stops directly at station N. For safety purposes, it is maintained that train B cannot depart from station i unless train A has already reached station (i+1) (1 ≤ i < N).

Find the minimum time after which train B reaches station N, once train A departs from station 1.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N, denoting number of stations.
- The next line contains N-1 space-separated integers, P_{1},P_{2},\ldots ,P_{N-1}.

------ Output Format ------ 

For each test case, output on a new line the minimum time after which train B reaches station N.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$1 ≤ P_{i} ≤ 10^{3}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
2
4
3
3 5
4
5 2 6

----- Sample Output 1 ------ 
8
13
19

----- explanation 1 ------ 
Test case $1$: $A$ reaches station $2$ at $t=4$ and at this time $B$ departs from station $1$ and reaches station $2$ at $t=4+4=8$.

Test case $2$: Following is the timeline of two trains-
- At $t=3$, $A$ reaches station $2$ and $B$ departs from station $1$.
- At $t=6$, $B$ reaches station $2$ but $A$ has not yet reached station $3$, so train $B$ will wait at station $2$.
- At $t=8$, $A$ reaches station $3$ and $B$ departs from station $2$.
- At $t=8+5=13$, train $B$ reaches station $3$.

Source: codechef | Difficulty: EASY


Solutions:
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	x = p[0]
	y = 2 * x
	for i in range(1, n - 1):
		x += p[i]
		if y < x:
			y += x - y + p[i]
		else:
			y += p[i]
	print(y)


for _ in range(int(input())):
	n = int(input())
	P = list(map(int, input().split()))
	a = b = P[0]
	b = b * 2
	for i in range(1, n - 1):
		a = a + P[i]
		if b < a:
			b = b + (a - b) + P[i]
		else:
			b = b + P[i]
	print(b)


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	A = B = L[0]
	B *= 2
	for i in range(1, N - 1):
		A += L[i]
		if B < A:
			B += A - B + L[i]
		else:
			B += L[i]
	print(B)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(max(l) + sum(l))


for _ in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	print(max(P) + sum(P))


T = int(input())
for i in range(0, T):
	N = int(input())
	buf = input().split(' ')
	P = [eval(j) for j in buf]
	time = sum(P) + max(P)
	print(time)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	print(max(a) + sum(a))


t = int(input())
while t > 0:
	n = int(input())
	x = input()
	l = x.split(' ')
	ans = 0
	Max = -1
	for i in l:
		ans = ans + int(i)
		if Max < int(i):
			Max = int(i)
	print(ans + Max)
	t -= 1


for _ in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	T_A = P[0]
	T_B = P[0]
	for i in range(1, N - 1):
		T_A = T_A + P[i]
		T_B = T_B + P[i - 1]
		if T_B < T_A:
			T_B = T_B + (T_A - T_B)
	print(T_B + P[N - 2])


for i in range(int(input())):
	n = int(input())
	p = [int(x) for x in map(int, input().split())]
	print(sum(p) + max(p))


t = int(input())
for tc in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	print(sum(p) + max(p))


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = lis[0]
	rem = 0
	for i in range(n - 2):
		if rem + lis[i] > lis[i + 1]:
			rem += lis[i] - lis[i + 1]
		else:
			rem = 0
		ans += lis[i + 1]
	ans += lis[-1] + rem
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp1 = sum(arr)
	temp2 = max(arr)
	jay = temp1 + temp2
	print(jay)


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	s = sum(p)
	a = max(p)
	print(s + a)


t = int(input())
for i in range(t):
	n = int(input())
	lst = sorted(list(map(int, input().split())), reverse=True)
	s = lst[0] + sum(lst)
	print(s)


T = int(input())
for i in range(T):
	x = int(input())
	y = list(map(int, input().split()))
	a = sum(y) + max(y)
	print(a)


t = int(input())
for i in range(t):
	N = int(input())
	N1 = list(map(int, input().split()))
	summ = sum(N1) + max(N1)
	print(summ)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a) + max(a)
	print(s)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	m = max(l)
	print(s + m)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(max(arr) + sum(arr))


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	p = tuple(map(int, sys.stdin.readline().split()))
	print(sum(p) + max(p))


for _ in range(int(input())):
	n = int(input())
	p = tuple(map(int, input().split()))
	print(sum(p) + max(p))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	suffix = [0] * n
	for i in range(1, n):
		suffix[i] = suffix[i - 1] + p[i - 1]
	a = b = 0
	idx = 0
	while idx <= n - 2:
		if a >= suffix[idx + 1]:
			a += p[idx]
			b += p[idx]
			idx += 1
		else:
			diff = abs(a - suffix[idx + 1])
			a += diff
			b += diff
	print(b)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(sum(a) + max(a))


import numpy as np
T = int(input())
for i in range(T):
	N = int(input())
	row = [int(x) for x in input().split()]
	p = np.array(row)
	A = sum(p) + max(p)
	print(A)


T = int(input())
for i in range(T):
	N = int(input())
	P = [int(item) for item in input().split(' ')]
	res = sum(P) + max(P)
	print(res)


t = int(input())
for ni in range(t):
	n = int(input())
	p = [int(i) for i in input().split()]
	(m, s) = (0, 0)
	print(sum(p) + max(p))


for _ in range(int(input())):
	n = int(input())
	ap = [int(x) for x in input().split()]
	bp = ap.copy()
	(ai, bi, t) = (0, 0, 0)
	i = 0
	while ai < n - 1:
		if ai == bi:
			t += ap[ai]
			ap[ai] = 0
			ai += 1
		elif ap[ai] < bp[bi]:
			t += ap[ai]
			bp[bi] -= ap[ai]
			ap[ai] = 0
			ai += 1
		elif ap[ai] > bp[bi]:
			t += bp[bi]
			ap[ai] -= bp[bi]
			bp[bi] = 0
			bi += 1
		else:
			t += ap[ai]
			(ap[ai], bp[bi]) = (0, 0)
			ai += 1
			bi += 1
	while bi < n - 1:
		t += bp[bi]
		bi += 1
	print(t)


for t in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	print(sum(x) + max(x))


import math
t = int(input())
for _ in range(t):
	n = map(int, input().split())
	p = list(map(int, input().split()))
	print(sum(p) + max(p))


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		P = list(map(int, input().split(' ')))[:N - 1]
		print(sum(P) + max(P))
main()


t = int(input())
while t:
	n = int(input())
	a = list((int(i) for i in input().split()))
	b = []
	b.append(a[0])
	for i in range(1, n - 1):
		b.append(a[i])
	for i in range(1, n - 1):
		b[i] = b[i] + b[i - 1]
	ct = 2 * a[0]
	for i in range(1, n - 1):
		if b[i] < ct:
			ct += a[i]
		else:
			ct += b[i] - ct
			ct += a[i]
	print(ct)
	t = t - 1


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))[:N - 1]
	print(sum(A) + max(A))


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	t = sum(l) + max(l)
	print(t)


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	t = 0
	for i in p:
		t += i
	print(t + max(p))


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	sum = 0
	for i in list1:
		sum += i
	print(sum + max(list1))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.insert(0, 0)
	delay = l[0]
	for i in range(1, n):
		if l[i] > delay:
			delay += l[i] - delay
	print(sum(l) + delay)


t = int(input())
while t > 0:
	n = int(input())
	pl = list(map(int, input().split()))
	x = sum(pl)
	y = x + max(pl)
	print(y)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	s = sum(p)
	print(s + max(p))


for _ in range(int(input())):
	N = int(input())
	P = list(map(int, input().split(' ', N - 1)))
	s = 0
	m = -1
	for i in P:
		s += i
		if i > m:
			m = i
	print(s + m)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input('').split()))
	sum1 = 0
	print(sum(l) + max(l))