#yukicoder3185 Three Abs

def solve(N, A):
    #A[:i], A[i: j], A[j:] に分割する。
    #note: 空区間ができたとき、総和を0としていいか？ → OK 明らかに最適解にならないから
    #でも実装の練習をしたいのでiはvalidな分割のみ認めることにする
    
    #jを全探索するとして、最適な分割点iを前計算しておきたい
    #sum maxとsum minのどちらかで区切ればいいんじゃないか？とエスパー
    #とにもかくにも累積和配列を作る
    C = [0] * (N + 1)
    for i, Ai in enumerate(A):
        C[i + 1] = C[i] + Ai

    #分割は |C[i] - C[0]| + |C[j] - C[i]| + |C[N] - C[j]| と書ける点に注意
    #jを全探索するとして、選べるiは[1, j)の範囲となる
    #j = 2 ～ N - 1を探索する
    Ci_min = Ci_max = C[1] - C[0]
    i_min = i_max = 1
    ans = - 1 << 63
    for j in range(2, N):
        ans = max(ans,
                  abs(Ci_min) + abs(C[j] - C[i_min]) + abs(C[N] - C[j]),
                  abs(Ci_max) + abs(C[j] - C[i_max]) + abs(C[N] - C[j]))
        if C[j] - C[0] < Ci_min:
            Ci_min, i_min = C[j] - C[0], j
        if C[j] - C[0] > Ci_max:
            Ci_max, i_max = C[j] - C[0], j
    return ans


for _ in range( T := int(input()) ):
    print( solve(N := int(input()), A := list(map(int, input().split()))) )