#include<bits/stdc++.h>
using namespace std;
long long n,t,a[300005],sum,ans,two;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;sum=0;ans=0;two=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]==2){
				sum+=2;two++;
			}
			else if(a[i]==1){
				sum++;
			}
		}
		for(int i=1;i<=n;i++){
			if(sum<a[i]/3){
				ans+=sum;
				a[i]-=sum*3;
				ans+=a[i]/4;
				sum=a[i]%4;
				if(sum>=2) two++;
			}
			else if(a[i]>=3){
				ans+=a[i]/3;
				sum+=a[i]%3;
				sum-=a[i]/3;
				if((a[i]%3)==2) two++; 
			}
		}
		if(sum>two*2){
			ans+=two+(sum-2*two);
		}
		else{
			ans+=sum/2;
			if(sum%2) ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}