#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio();
    cin.tie(),cout.tie();
    int T;
    cin>>T;
    while(T--){
        long long fc=0,n,f=0,s=0,t=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            int v;
            cin>>v;
            if(v%4==0&&v!=0)  fc+=(v/4);
            else{
                if(v%3==0) t+=(v/3);
                else if(v%3==1) t+=(v/3),f++;
                else t+=(v/3),s++;
            }
        }
        if(f>=t){
            fc+=(f+s);
            cout<<fc<<"\n";
            continue;
        }
        else{
			fc+=f,t-=f;
			if(2*s<=t){
				fc+=(2*s);
				t-=(2*s);
				fc+=(t/4*3);
				t%=4;
				if(t==1||t==2) fc+=2;
				if(t==3) fc+=3;
				cout<<fc<<"\n";
				continue;
			}
			else{
				if(t%2==1)	fc+=2,s--,t--;
				fc+=t;
				s-=(t/2);
				fc+=s;
				cout<<fc<<"\n";
				continue;
			}
        }
    }
}