#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve()
{
    ll n;
    cin >> n;
    vector<ll> arr(n);
    for (auto &e : arr)
    {
        cin >> e;
    }

    ll ans = 0;

    priority_queue<ll> oddHeap;
    priority_queue<ll, vector<ll>, greater<ll>> evenHeap;

    for (auto e : arr)
    {
        if (e & 1)
        {
            oddHeap.push(e);
        }
        else
        {
            evenHeap.push(e);
        }
    }

    while (!oddHeap.empty() && !evenHeap.empty())
    {
        ll odd = oddHeap.top();
        oddHeap.pop();
        ll even = evenHeap.top();
        evenHeap.pop();

        if (odd < even)
        {
            oddHeap.push(odd + even);
            evenHeap.push(even);
        }
        else
        {
            oddHeap.push(odd);
            oddHeap.push(odd + even);
        }

        ++ans;
    }

    cout << ans << '\n';
}

int main()
{
    ll t;
    cin >> t;
    for (int it = 1; it <= t; it++)
    {
        solve();
    }
    return 0;
}