Coach Moony wants the best team to represent their college in ICPC. He has $N$ students standing in a circle with certain rating $X_i$ on a competitive coding platform. It is an established fact that any coder with more rating on the platform is a better coder.      
Moony  wants to send his best $3$ coders based upon their rating. But all coders only want to have their friends in their team and every coder is friends with four other coders, adjacent two on left side in the circle, and adjacent two on right. So Moony comes up with a solution that team with maximum cumulative rating of all three members in a team shall be representing their college.
You need to give the cumulative score of the team that will be representing the college.

-----Input:-----
- First line will contain $T$, number of testcases. 
- First line of each test case contains a single integer $N$.
- Second  line of each test case takes $N$ integers, denoting rating of $ith$ coder.

-----Output:-----
For each testcase, output a single integer denoting cumulative rating  of the team.

-----Constraints-----
- $1 \leq T \leq 10$
- $7 \leq N \leq 10^5$ 
- $0 \leq X_i \leq 10^9$

-----Sample Input:-----
1

7

10 40 30 30 20 0 0  

-----Sample Output:-----
100

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
T = int(input())
for i in range(T):
	(N, data) = (int(input()), list(map(int, input().split())))
	if N == 3:
		print(sum(data))
	else:
		best = data[0] + data[1] + data[2]
		overall = best
		k = len(data)
		for i in range(1, k - 2):
			overall = overall - data[i - 1] + data[i + 2]
			if overall > best:
				best = overall
		j = max(data[1], data[-2])
		l = data[-1] + data[0] + j
		if best < l:
			best = l
		print(best)


def func(n, l):
	if n <= 3:
		return sum(l)
	else:
		s = 0
		for i in range(n - 2):
			temp = sum(l[i:i + 3])
			if temp > s:
				s = temp
		temp = l[n - 1] + l[0] + l[1]
		if temp > s:
			s = temp
		temp = l[n - 1] + l[n - 2] + l[0]
		if temp > s:
			s = temp
		return s
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(func(n, l))


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr_sum = []
	for i in range(len(arr)):
		arr_sum.append(arr[i] + arr[(i + 1) % n] + arr[(i + 2) % n])
	print(max(arr_sum))


t = int(input())
for s in range(0, t):
	n = int(input())
	l = list(map(int, input().strip().split()))
	a = len(l)
	i = 0
	max = -999999
	while i < a:
		sum = 0
		if i == a - 1:
			sum = l[i] + l[0] + l[1]
		elif i == a - 2:
			sum = l[i] + l[i + 1] + l[0]
		else:
			sum = l[i] + l[i + 1] + l[i + 2]
		if sum > max:
			max = sum
		i = i + 1
	print(max)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().strip().split()))
	if n == 3:
		print(sum(l))
	else:
		ans = 0
		for j in range(n):
			p = l[j] + l[(j + n + 1) % n] + l[(j + n + 2) % n]
			if p > ans:
				ans = p
		p = l[n - 2] + l[n - 1] + l[0]
		if p > ans:
			ans = p
		p = l[1] + l[n - 1] + l[0]
		if p > ans:
			ans = p
		print(ans)


from sys import stdin, stdout
s = ''
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	m = 0
	for i in range(-1, n - 2):
		x = a[i] + a[i + 1] + a[i + 2]
		if m < x:
			m = x
	x = a[n - 2] + a[n - 1] + a[0]
	if m < x:
		m = x
	s += str(m) + '\n'
stdout.write(s)


t = int(input())
while t > 0:
	n = int(input())
	li = list(map(int, input().strip().split()))[:n]
	sum = 0
	start = 0
	end = 3 - 1
	for i in range(3):
		sum += li[i]
	ans = sum
	for i in range(3, n + 3):
		sum += li[i % n] - li[(i - 3) % n]
		if sum > ans:
			ans = sum
			start = (i - 3 + 1) % n
			end = i % n
	print(ans)
	t = t - 1


import sys
tt = int(sys.stdin.readline())
for _ in range(tt):
	nn = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	maxx = arr[0] + arr[1] + arr[2]
	summ = maxx
	for i in range(nn - 3):
		summ = summ - arr[i] + arr[i + 3]
		maxx = max(summ, maxx)
	if arr[-1] + arr[-2] + arr[0] > maxx:
		maxx = arr[-1] + arr[-2] + arr[0]
	print(maxx)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	x.append(x[0])
	x.append(x[1])
	n += 2
	s = 0
	if n <= 3:
		print(sum(x))
		continue
	for i in range(n - 3):
		if sum(x[i:i + 3]) > s:
			s = sum(x[i:i + 3])
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = []
	for j in range(n):
		m = sum([arr[j % n], arr[(j + 1) % n], arr[(j + 2) % n]])
		ans.append(m)
	print(max(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	max_rating = 0
	arr = list(map(int, input().split()))
	for i in range(1, len(arr)):
		if i < n - 1:
			x = arr[i - 1] + arr[i] + arr[i + 1]
		else:
			x = arr[i - 1] + arr[i] + arr[(i + 1) % n]
		max_rating = max(x, max_rating)
	print(max_rating)


T = int(input())
for t in range(T):
	N = int(input())
	X = list(map(int, input().split()))
	mx = 0
	for i in range(N):
		if mx < X[i % N] + X[(i + 1) % N] + X[(i + 2) % N]:
			mx = X[i % N] + X[(i + 1) % N] + X[(i + 2) % N]
	print(mx)


t = int(input())
for _ in range(t):
	l = []
	n = int(input())
	temp = list(map(int, input().split()))
	l = temp[n - 2:n]
	l.extend(temp)
	l.extend(temp[:3])
	tx = sum(l[:3])
	mx = tx
	for i in range(3, len(l)):
		mx = max(mx, tx - l[i - 3] + l[i])
		tx = tx - l[i - 3] + l[i]
	print(mx)


J = int(input())
for i in range(J):
	(N, data) = (int(input()), list(map(int, input().split())))
	if N == 3:
		print(sum(data))
	else:
		best = data[0] + data[1] + data[2]
		overall = best
		for i in range(1, len(data) - 2):
			overall = overall - data[i - 1] + data[i + 2]
			if overall > best:
				best = overall
		if best < data[-1] + data[0] + max(data[1], data[-2]):
			best = data[-1] + data[0] + max(data[1], data[-2])
		print(best)