#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e6+10;
int a[maxn],biao[maxn+10] = {2},cnt1,cnt2,cnt3,t,n;

signed main(){
	cin >> t;
	biao[0] = 0,biao[1] = 2;
	for(int i = 2;i <= 20;i++){
		biao[i] = biao[i - 1];
		if((i - 1) % 4 == 0) biao[i] += 2;
		else if((i - 1) % 2 == 0) biao[i] += 1;
	} 
	while(t--){
		cin >> n;
		int ans = 0;
		cnt1 = 0,cnt2 = 0,cnt3 = 0;
		for(int i = 1;i <= n;i++) cin >> a[i];
		for(int i = 1;i <= n;i++){
			if(a[i] == 0) continue;
			cnt3 += (a[i] / 3);
			if(a[i] % 3 == 1) cnt1++;
			else if(a[i] % 3 == 2) cnt2++;	
		}
		if(cnt1 >= cnt3){
			cout << cnt1 + cnt2 << '\n';
		}else{
			cnt3 -= cnt1;
			ans += cnt1;
			if(cnt3 % 2 == 0){
				if(cnt2 * 2 >= cnt3){
					ans += cnt3;
					ans += cnt2 - (cnt3 / 2);
				}else{
					cnt3 -= cnt2 * 2;
					ans += cnt2 * 2 + biao[cnt3 % 4]  + biao[4] * (cnt3 / 4);
				}
			}else{
				if(cnt2 * 2 >= cnt3){
					ans += cnt3 - 1;
					ans += 2;
					ans += (cnt2 - 1 - cnt3 / 2); 
				}else{
					ans += (cnt2 * 2);
					cnt3 -= cnt2 * 2;
					ans += biao[cnt3 % 4] + biao[4]  * (cnt3 / 4);
				}
			}
			cout << ans << '\n';
		}
	}
	return 0;
}