Nutanix has clusters on whcih virtual machines (consider a virtual computer system) can be created.
Nutanix provides interstellar disaster recovery soltion. Now the problem is, there are virtual machines running on a cluster in Keplar-452b, the sun in solar system of Keplar-452b is about to collapse into singularity (blackhole), before that we need to send data of all the virtual machines to Earth or Proxima Centauri, via a technology developed by Nutanix which sends data through Einstein-Roseberg bridge (wormhole) so it does not take millions of light years to reach earth.

You should divide data send to Earth and Proxima Centauri, such that it takes minimum time. Consider the rate at which data is transferred to both planets from Keplar-452b is 1 TB/s each simultaneously. There are N virtual machines, i th virtual machine had data d[ i ] TB to be transferred.

Input:
First line contains a single integer T, the number of test cases.
For each test case first line contains a single integer N, the number of virtual machines. Next line contains N integers, ith integer d[i] decribes amount of data in ith virtual machine.

Output:
For each test case print a single integer, the minimum time in seconds required to transfer all the data, in a separate line.

Constraints:
1<=T<=5
1<=N<=1000
1<=d[i]<=100

Example-
Input:
1
5
1 2 3 4 5

Output:
8

Explanaton:
Given 5 virtual machine with data 1, 2, 3, 4, 5 in TBs.
You can send data from virtual machine [1, 2, 4] (= 1 + 2 + 4 = 7TB of data will take 7 seconds @ 1TBps) on Earth and [3,5] ( = 3 + 5 = 8TH of data @1TBps will take 8 seconds) on Proxima Centauri so total time taken is max(7,8) = 8 seconds.