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

int T,n,ans;
int v[600005];

bool cmp(int a,int b)
{
	return a > b;
}

bool cmpp(int a,int b)
{
	return a % 3 < b % 3;
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	//freopen("card3.in","r",stdin);
	
	cin>>T;
	while(T --)
	{	
		ans = 0;
		memset(v,0,sizeof v);
		
		cin>>n;
		for(int i = 1;i <= n;i ++)
			cin>>v[i];
		
		sort(v + 1,v + n + 1,cmp);
		int x = upper_bound(v + 1,v + n + 1,3,greater <int> ()) - v;
		x --;
		sort(v + 1,v + x + 1,cmpp);//把>3里面%3为1的排在最前面
								   //这样在消耗小数时能优先消耗1，之后消耗2 
		
		int l = 1,r = n;//l，r分别为数组头，尾 
		for(int i = 1;i <= r;i ++)
		{
			if(v[i] < 3)continue;
			
			int sum = v[i] / 3;
			ans += sum;
			v[i] %= 3;
			l ++;//算过了，头++ 
			if(v[i])//在余数非零时把余数移到数组尾 
			{
				int j = upper_bound(v + l,v + r + 1,v[i],greater <int> ()) - v;
				v[++r] = v[j];
				v[j] = v[i];
			}
			
			//从后往前消耗小数 
			while(v[r] <= sum && i < r)
				sum -= v[r],v[r --] = 0;
			if(i == r)
			{
				ans -= sum;
				v[i] += sum * 3;
				l --;
				
				break;
			}
			else v[r] -= sum;
		}
		
		for(int i = l;i <= r;i ++)
		{
			ans += v[i] / 2;
			v[i] %= 2;
			ans += v[i];
		}
		
		cout<<ans<<'\n';
	}
	return 0;
}
/*
1
50
3 3 0 0 0 0 3 0 0 0 3 3 0 0 3 0 6 0 3 0 0 0 0 3 1 1 1 4 1 1 7 4 1 1 1 4 4 1 1 1 10 2 5 2 2 2 2 2 2 2

*/