#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
long long a[MAXN];
int main()
{
    int T,n;
    long long sum = 0;
    long long cnt1 = 0 , cnt2 = 0 , cnt3 = 0;
    cin >> T; // 输入询问次数
    for (int t = 1 ; t <= T ; ++t)
	{
        memset(a,0,sizeof(a));
        cnt1 = cnt2 = cnt3 = sum = 0;
        cin >> n;
        for (int i = 1 ; i <= n ; ++i)
		{
            cin >> a[i]; // 输入每种牌的数量
            sum += a[i];
            cnt3 += a[i]/3;// 累加可以组成三张的组合
        }
        if (cnt3 > sum/4) // 如果所有“三张”的总数足以覆盖至少四张一组的分布
		{
            if (sum % 4 == 1) cout << sum / 4 + 1 << endl;
            else if (sum % 4 ==2) cout << sum / 4 + 1 << endl;
            else if (sum % 4 == 3) cout << sum / 4 + 2 << endl;
            else if (sum % 4 == 0) cout << sum / 4 << endl;
        }
        else if (cnt3 <= sum/4)
		{
            for (int i = 1 ; i <= n ; i++)
			{
                if (a[i] % 3 == 1) cnt1++;// 模 3 余 1 的牌数量
                else if (a[i] % 3 == 2) cnt2++;// 模 3 余 2 的牌数量
            }
            if (cnt3 <= cnt1) cout << cnt1 + cnt2 << endl;// 如果“三张”不足够，使用余数牌
            else if (cnt3 > cnt1) cout << cnt3 + cnt2 - (cnt3 - cnt1) / 2 << endl;// 用余数的 2 补充“三带一”或其他牌
        }
    }

    return 0;
}