#include<bits/stdc++.h>
using namespace std;
int T,n,x;
long long a[4],ans;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		ans=a[1]=a[2]=a[3]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			a[3]+=x/3;
			a[x%3]++;
		}
		if(a[1]<a[3])
		{
			a[3]-=a[1];
			ans+=a[1];
			a[1]=0;
		}
		else
		{
			a[1]-=a[3];
			ans+=a[3];
			a[3]=0;
		}
		if((a[1])||(a[1]==a[3]&&a[1]==0))ans+=a[1]+a[2];
		else
		{
			if(a[2]*2<a[3])
			{
				ans+=a[2]*2;
				a[3]-=a[2]*2;
				a[2]=0;
			}
			else
			{
				ans+=a[3];
				if(a[3]%2==0)a[2]-=a[3]/2;
				else
				{
					a[2]-=a[3]/2-1;
					a[1]++;
				}
				a[3]=0;
			}
			if(a[3])
			{
				ans+=a[3]*3/4;
				if(a[3]*3%4==3)ans+=2;
				if(a[3]*3%4==1)ans++;
				if(a[3]*3%4==2)ans++;
			}
			else ans+=a[1]+a[2];
		}
		printf("%lld\n",ans);
	}
	return 0;
}