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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    cin >> T;
    while(T--){
        int N; 
        cin >> N;
        long long cPos = 0, cNeg = 0, cZero = 0;

        for(int i=0; i<N; i++){
            int x; 
            cin >> x;
            if(x == 1)      cPos++;
            else if(x == -1) cNeg++;
            else            cZero++;
        }

        long long score = 0;

        {
            long long x = min(cPos, cNeg/2);
            score += x;
            cPos  -= x;
            cNeg  -= 2*x;
        }

        {
            long long y = cPos / 3;
            score += y;
            cPos  -= 3*y;
        }

        {
            long long z = min(cZero, cNeg/2);
            cNeg  -= 2*z;
            cZero -= z;
        }

        {
            long long w = cNeg / 3;
            score -= w;
            cNeg  -= 3*w;
        }

        auto product3 = [&](int a, int b, int c){
            return 1LL * a * b * c;
        };

        long long leftoverCombos = (cPos + cNeg + cZero) / 3;

        while(leftoverCombos > 0){

            long long bestGain = -1e15;
            tuple<int,int,int> bestPick = {0,0,0}; 


            for(int p=0; p<=2; p++){
                for(int n=0; n<=2; n++){
                    for(int z=0; z<=3; z++){
                        if(p + n + z == 3){
                            if(p <= cPos && n <= cNeg && z <= cZero){
                                long long val = product3(
                                    p>0 ? 1 : (n>0 ? -1 : 0),
                                    p>1 ? 1 : (n>1 ? -1 : (z>0 ? 0 : 0)),

                                    (p + n + z >= 3 ? 
                                     (p==3 ? 1 
                                      : (n==3 ? -1 
                                         : 0)) : 0)
                                );

                                long long actualProduct = 0;
                                if(z>0){
                                    actualProduct = 0;
                                } else {
                                    if(n % 2 == 0) actualProduct = 1;
                                    else          actualProduct = -1;
                                }
                                if(actualProduct > bestGain){
                                    bestGain = actualProduct;
                                    bestPick = {p,n,z};
                                }
                            }
                        }
                    }
                }
            }

            if(bestGain == -1e15){
                break;
            }

            score += bestGain;
            auto [pp,nn,zz] = bestPick;
            cPos  -= pp;
            cNeg  -= nn;
            cZero -= zz;
            leftoverCombos--;
        }

        cout << score << "\n";
    }

    return 0;
}