def findPath(nums):
    if not nums:return 0
    if len(nums)==1:return nums[0]
    if len(nums)==2:return max(nums)
    if len(nums)==3:return sum(nums)
    n=len(nums)
    stage1=nums[0]+nums[1]+nums[-1]+nums[1]
    stage2=nums[0]+nums[-1]+nums[0]+nums[-2]
    return min(stage1,stage2)+findPath(nums[:n-2])
k=int(input())
for _ in range(k):
    n=int(input())
    nums=sorted(list(map(int,input().split(" "))))
    print(findPath(nums))