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