Untitled

#include <iostream>
#include <cmath>
#include <set>
#define int long long
using namespace std;

signed main () {
    int t; cin>>t;
    while (t--) {
        int n;
        cin>>n;
        multiset<int> st;
        for (int i=0; i<n; i++) {
            int x; cin>>x;
            st.insert(x);
        }
        int ans = 0;
        int x = 0;
        while (!st.empty()) {

            while (true) {

                int num = *(st.begin());
                int maxm = *(st.rbegin());
                if (num+x > maxm) break;
                st.erase(*st.begin());
                x += num;
                ans += num;
            }

            if (st.size() > 1) {
                int num = *(st.begin());
                int maxm = *(st.rbegin());
                int pending = maxm - x;

                ans += pending;

                st.erase(*st.begin());
                st.erase(*st.rbegin());
                ans++;
                if (num - pending) st.insert(num - pending);
                x=0;
            }

            else {
                int num = *(st.begin());
                int diff = num - x;
                diff /= 2;
                x += diff;
                ans += diff;
                num -= diff;
                if (num != x) {
                    ans++;
                    ans++;
                }
                else ans++;
                break;
            }
            
        }
        cout << ans << "\n";
    }
}