#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main()
{
    faster
    int t ;
    cin >> t ;
    while(t--)
    {
        int n;
        cin >> n;
        int arr[n+7];
        int sum=0;
        for(int i=0; i<n; i++)
        {
            cin >> arr[i];
            sum+=arr[i];
        }
        if(sum%3==0)
        {
            cout << n << endl;
            continue;
        }
        int ex=sum%3;
        for (int i = 1; i < n; ++i)
        {
            int sum2 = 0;
            for (int j = 0; j < i; ++j)
            {
                sum2+=arr[j];
            }
            if (sum2%3==ex)
            {
                cout << n-i << endl;
                return 0;
            }
        }
    }
}