for cas in xrange(input()):
    n = input()
    a = map(int, raw_input().strip().split())
    pref = [0]*n
    suff = [0]*n
    curr = 0
    for i in xrange(n):
        pref[i] = curr = max(curr, 0) + a[i]
    curr = 0
    for i in xrange(n-1,-1,-1):
        suff[i] = curr = max(curr, 0) + a[i]
    print max(pref + suff + [pref[i-1] + suff[i+1] for i in xrange(1,n-1)])