#include<stdio.h>
int main ()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,sum=0;
        scanf("%d",&n);
        int arr[n];
        for(int i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
            sum += arr[i];
        }
        int x = sum%3 ;
        int i=0,j=n;
        while(i<=j)
        {
            if(x == arr[i])
            {
                printf("1\n");
                break;
            }
            i++ ;
        }
        if(x==0)
        {
            printf("0\n");
        }
        else if(x==2)
        {
             printf("1\n");
        }
 
        else 
        {
             printf("2\n");
        }
 
    }
    return 0;
}

I2luY2x1ZGU8c3RkaW8uaD4KaW50IG1haW4gKCkKewogICAgaW50IHQ7CiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBpbnQgbixzdW09MDsKICAgICAgICBzY2FuZigiJWQiLCZuKTsKICAgICAgICBpbnQgYXJyW25dOwogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgewogICAgICAgICAgICBzY2FuZigiJWQiLCZhcnJbaV0pOwogICAgICAgICAgICBzdW0gKz0gYXJyW2ldOwogICAgICAgIH0KICAgICAgICBpbnQgeCA9IHN1bSUzIDsKICAgICAgICBpbnQgaT0wLGo9bjsKICAgICAgICB3aGlsZShpPD1qKQogICAgICAgIHsKICAgICAgICAgICAgaWYoeCA9PSBhcnJbaV0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHByaW50ZigiMVxuIik7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBpKysgOwogICAgICAgIH0KICAgICAgICBpZih4PT0wKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbnRmKCIwXG4iKTsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZih4PT0yKQogICAgICAgIHsKICAgICAgICAgICAgIHByaW50ZigiMVxuIik7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGVsc2UgCiAgICAgICAgewogICAgICAgICAgICAgcHJpbnRmKCIyXG4iKTsKICAgICAgICB9CiAgICAgICAgCiAgICB9CiAgICByZXR1cm4gMDsKfQ==

OAo0CjIgMiA1IDQKMwoxIDMgMgo0CjMgNyA2IDgKMQoxCjQKMiAyIDQgMgoyCjUgNQo3CjIgNCA4IDEgOSAzIDQKMgo0IDEwCg==

8
4
2 2 5 4
3
1 3 2
4
3 7 6 8
1
1
4
2 2 4 2
2
5 5
7
2 4 8 1 9 3 4
2
4 10