#include <bits/stdc++.h>
using namespace std;

// [1] arr数组-存储每个州的选民人数，最多支持200个元素（适配n≤101的数据范围）
int arr[200];

int main(){
    // [2] t-测试用例的组数（1 < n < 100）
	int t;
	cin>>t;
    // [3] 处理每组测试用例
	while(t--) {
        // [4] n-当前测试用例中的州的数量（1 ≤ m ≤ 101）
		int n;
		cin>>n;
        // [5] 读取n个州的选民人数，存入arr数组
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
        // [6] 对州的选民人数进行升序排序：贪心策略的核心，优先选择选民数最少的州（因为这些州用最少的选民就能拿到支持，从而总选民数最少）
		sort(arr,arr+n);
			
        // [7] sum-累计需要的最少选民数，初始为0
		int sum=0;
        // [8] 计算需要的州数：超过一半的州支持即可当选，即需要 (n/2 +1) 个州（如n=3需要2个，n=5需要3个）
        // 遍历前 (n/2 +1) 个州（选民数最少的州），计算每个州需要的选民数（超过该州选民数的一半：arr[i]/2 +1）
		for(int i=0;i<=n/2;i++){
			sum=sum+arr[i]/2+1;
		}
        // [9] 输出当前测试用例需要的最少选民数
		cout<<sum<<endl;	
	}
}