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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
#Moony and ICPC team
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(l[0]+l[1]+l[2])
    elif(n==4):
        print(sum(l)-min(l))
    else:
        ans=0
        for i in range(n):
            k = [0 for i in range(5)]
            k[0]=l[i]
            k[1]=l[(i+n+1)%n]
            k[2] = l[(i+n+2)%n]
            k[3] = l[i-1]
            k[4] = l[i-2]
            k.sort()
            p = k[2]+k[3]+k[4]
            if(p>ans):
                ans=p
        print(ans)'''
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)
    
            


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

try:
    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)
except:
    pass

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 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)

# cook your dish here
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





# cook your dish here
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)

# cook your dish here
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)

# cook your dish here
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)

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)

try:
    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)
except:
    pass


try:
    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)
except:
    pass


# cook your dish here
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
        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)

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))


# cook your dish here
import sys

t=int(sys.stdin.readline())

for _ in range(t):
    n=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(n-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)

# cook your dish here
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) 

# cook your dish here
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)

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)