#include <stdio.h>
int main(){
    
    //SAYED AL MAMUN_LU
    
    int t;
    scanf("%d",&t);
    
    while(t--){
        int sum = 0,yy = 0,yy1 = 0;
        int flag = 0;
        int n;
        scanf("%d",&n);
        
        
        int samp[n];
        for(int i = 0; i<n; i++){
            scanf("%d",&samp[i]);
        }
        
        for(int i = 0; i<n; i++){
            yy = yy + 1;
            yy1 = yy1 + samp[i];
            if(samp[i]%3 == 0){
                sum = sum + 1;
                
            }
            else {
                flag = flag + samp[i];
            }
        }
        
       if(yy1%3 == 0) {
            printf("%d\n",yy);
        }
        else {
            printf("%d\n",1);
        }
    }
  
    
}