I=input
for t in [0]*int(I()):
	N=I()
	A=sorted(map(int,I().split()))
	a,b,r=0,1,A[-1]
	for x in A[-2::-1]:
		if r<x:a,b,r=a+2*r,0,x-r
		else:a,r=a+2*x,r-x
	print(a+[r,min(r,1)][b])