先考虑两个数字的情况，设只有两个数字 $a, b$，不妨设 $(a + b) \mod 2 = 0$，可以猜到当大招的价值是 $x = \frac{a + b}{2}$ 的时候，操作数最小，此时答案是 $ans = x + 1$。下面用反证法，设大招的价值是 $y < x$，那么还剩 $a + b - 2 \cdot y$ 需要平 A，总的代价是 $ans_1 = a + b - 2y + y + 1 = a + b - y + 1 = 2x - y + 1 = x + 1 + (x - y)$，由于 $x > y$，所以 $ans_1 > ans$。

又由于价值为 $x$ 的大招并不能一次完成，因为并不能用一个大招消除掉所有的数字，例如 $8$，并不能一次消除掉 $3, 5$，每一群需要逐个消除，每一群都会额外贡献 1 的代价。为了保证 $x$ 里面的价值不浪费，从大到小排序，消耗 $x$，直到把 $x$ 消耗完。剩下的就是平 A 的代价。

// Date: Wed Dec 27 14:16:40 2023

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <functional>

using namespace std;

const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const double eps = 1e-8;
const int dir[8][2] = {
{0, 1}, {0, -1},
{1, 0}, {-1, 0},
{1, 1}, {1, -1},
{-1, 1}, {-1, -1},
};

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<int, int> PII;

const ull Pr = 131;

#define For(i, a, b) for (int i = int(a); i < int(b); ++i)
#define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i)
#define For1(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i)
#define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i])

#define f1 first
#define f2 second
#define pb push_back
#define has(a, x) (a.find(x) != a.end())
#define nonempty(a) (!a.empty())
#define all(a) (a).begin(),(a).end()
#define SZ(a) int((a).size())

template <typename t> istream &operator>>(istream &in, vector<t> &vec) {
    for (t &x : vec)
        in >> x;
    return in;
}

template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) {
    int n = SZ(vec);
    For(i, 0, n) {
        out << vec[i];
        if (i < n - 1)
            out << ' ';
    }
    return out;
}

#ifdef _DEBUG
#define debug1(x) cout << #x" = " << x << endl;
#define debug2(x,y) cout << #x" = " << x << " "#y" = " << y << endl;
#define debug3(x,y,z) cout << #x" = " << x << " "#y" = " << y << " "#z" = " << z << endl;
#else
#define debug1
#define debug2
#define debug3
#endif


const int N = 200010;
int t, n, a[N];

int main(void)
{
#ifdef _DEBUG
    freopen("1891c.in", "r", stdin);
#endif
    std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> t;

    while (t--) {
        cin >> n;

        ll sum = 0;
        For1(i, 1, n) cin >> a[i], sum += a[i];
        ll top = sum / 2, res = 0;
        sort(a + 1, a + 1 + n, greater<int>());
        For1(i, 1, n) {
            if (!top) {
                break;
            }
            if (top >= a[i]) {
                top -= a[i];
                a[i] = 0;
                res++;
            } else {
                a[i] -= top;
                top = 0;
                res++;
            }
        }
        For1(i, 1, n) if (a[i]) res += a[i];
        cout << res << '\n';
    }

    return 0;
}