#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e6 + 5;

ll a[MAXN];

void solve(void)
{
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		scanf("%lld",&a[i]);
	
	vector<ll> vec[4];
	for(int i=1; i<=n; ++i)
		vec[a[i] % 4].emplace_back(a[i]);
	
	auto upd = [&] (int i,int j)
	{
		ll x = vec[i].back(); vec[i].pop_back();
		ll y = vec[j].back(); vec[j].pop_back();
		
		ll z = (x + y) / 2;
		vec[z % 4].emplace_back(z);
	};
	while(vec[0].size() >= 2 || vec[2].size() >= 2)
	{
		if(vec[0].size() >= 2) upd(0, 0);
		if(vec[2].size() >= 2) upd(2, 2);
	}
	while(vec[0].size() && vec[2].size()) upd(0, 2);
}

int main(void)
{
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}