#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define dbg(a,b,c,d) cerr<<a<<"  "<<b<<"  "<<c<<"  "<<d<<endl;
#define kill(a) {cout<<a<<endl;continue;}
#define KILL(a) {cout<<a<<endl;return 0;}
#define debug cerr<<"Error Found"<<endl;
#define mem(a,b) memset(a,b,sizeof(a))
#define lcm(a, b) (a/__gcd(a,b))*b
#define w(t) cin>>t;while(t--)
#define pi  2 * acos(0.0)
#define endl "\n"
int t, cs = 0;
const int mxn = 1e4 + 3, mod = 1e9 + 7;
int dp[3][mxn], vis[3][mxn];
int n, ar[mxn];
int rec(int idx, int mo)
{
    if(idx == n)return (!mo ? 0 : -1e9);
    if(vis[mo][idx] == cs)return dp[mo][idx];
    vis[mo][idx] = cs;

    int ans = 1 + rec(idx + 1, (mo + ar[idx]) % 3);
    ans = max(ans, rec(idx + 1, mo));
    return dp[mo][idx] = ans;
}
int32_t main()
{

    fast
    w(t)
    {
        cin >> n;
        cs++;
        for(int i = 0; i < n; i++)cin >> ar[i];
        cout << rec(0, 0) << endl;
    }
}