for t in range(int(input())):
  N=int(input())
  A=[0]+sorted(map(int,input().split()))
  B=[]
  for i in range(N,0,-1):
    B.append(A[i]-A[i-1])
  print(sum(sorted(B)[N>>1:]))