#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        int N;
        scanf("%d", &N);
        int arr[N];
        int i, sum = 0, count = 0;

        for (i = 0; i < N; i++) {
            scanf("%d", &arr[i]);
            sum += arr[i];
        }

        
        if (sum % 3 == 0) {
            printf("%d\n", N); 
        } else {
            
            int remainder = sum % 3;

            
            for (i = 0; i < N; i++) {
                if (arr[i] % 3 == remainder) {
                    count++;
                    break; 
                }
            }

            if (count > 0) {
                printf("%d\n", N - 1); 
            } else {
                printf("0\n"); 
            }
        }
    }

    return 0;
}