using namespace std;
#define ll long long
const int nx=3e5+5;
int n,T;
ll a[nx],ans,ct[5];

void work(){
	memset(a,0,sizeof(a));
	memset(ct,0,sizeof(ct));
	ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ct[3]+=(a[i]/3); 
		if(a[i]%3==0)continue;
		ct[a[i]%3]++;
	}
	//cout<<ct[1]<<" "<<ct[2]<<" "<<ct[3]<<endl<<endl;
	if(ct[1]>=ct[3])ans=ct[1]+ct[2];
	else{
		ans+=ct[1];
		ct[3]-=ct[1];
		if(ct[3]&1==0){
			if(ct[3]<=2*ct[2]){
				ans+=ct[3];
				ct[2]-=ct[3]/2;
				ans+=ct[2]; 
			}
			else{
				ct[3]-=2*ct[2];
				ans+=ct[2]*2;
				if(ct[3]%4==3){
					ans+=(3+ct[3]/4*3);
				}
				else if(ct[3]%4==0){
					ans+=(ct[3]/4*3);
				}
				else {
					ans+=(2+ct[3]/4*3);
				}
			}
		}
		else {
			if(ct[3]-1<=2*ct[2]){
				ans+=ct[3]-1;
				ct[2]-=ct[3]/2;
				ans+=ct[2]; 
				ans+=1;
			}
			else{
				ct[3]-=2*ct[2];
				ans+=ct[2]*2;
				if(ct[3]%4==3){
					ans+=(3+(ct[3]/4)*3);
				}
				else if(ct[3]%4==0){
					ans+=((ct[3]/4)*3);
				}
				else {
					ans+=(2+(ct[3]/4)*3);
				}
			}
		}
	}
	cout<<ans<<endl;
}
int main(){
	//freopen("try.in","r",stdin);
	//freopen("try.out","w",stdout);
	cin>>T;
	for(int ii=1;ii<=T;ii++){
		work();
	}
} ```