#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=3e5+50; 
ll t,n,m,tp[N],ans;

int main(){
	scanf("%lld",&t);
	while(t--){
		ans=0;
		memset(tp,0,sizeof(tp));
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++){
			ll x;
			scanf("%lld",&x);
			if(x<=3)tp[x]++;
			else tp[3]+=x/3,tp[x%3]++;
		}
		if(tp[1]==tp[3])ans=tp[1]+tp[2];//3被1消 
		else if(tp[1]>tp[3])ans=tp[1]+tp[2];//3被1消 
		else{
			if(tp[1]>0)ans+=tp[1],tp[3]-=tp[1];//1被3消 
			if(tp[2]>0)ans+=max(0ll,tp[2]+tp[3]-tp[3]/2),tp[3]-=tp[2]*2;//2被3消 
			if(tp[3]>0){
				ans+=tp[3]/4*3,tp[3]%=4;//3被3消 
				if(tp[3]==1)ans+=2;//1个3要两次 
				else ans+=tp[3];
			}
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}