for _ in range(int(input())):
    x=int(input())
    y=map(int,input().split())
    pos=[]
    neg=[]
    for t in y:
        if t>0:
            pos.append(t)
        else:
            neg.append(t)
    if len(pos)==0:
        print(min(neg))
    elif len(neg)==0:
        print(max(pos))
    else:
        pos=sorted(pos,reverse=True)
        neg=sorted(neg)
        s=[pos[i]+neg[i] for i in range(x//2)]
        print(sum(s))