int main(int argc, char const* argv[])
{
    unsigned long long ans[41];
    ans[0] = 1;
    ans[1] = 1;
    ans[2] = 5;
    for(int i = 3;i <= 40;i++){
        ans[i] = ans[i-1]+4*ans[i-2]+2*ans[i-3];
    }
    int t;
    while(~scanf("%d",&t)){
        while(t--){
            int n;
            scanf("%d",&n);
            printf("%llu\n",ans[n]);
        }
    }

    return 0;
}

int main(int argc, char const* argv[])
{
    int p;
    //just sorting and scan the list
    while(scanf("%d",&p) != EOF){
        for(int i = 0;i<p;i++){
            multimap<int,char> ans;
            int n;
            scanf("%d",&n);
            for(int j =0;j<n;j++ ){
                int f;
                scanf("%d",&f);
                if(f>0)
                    ans.insert(pair<int,char>(f,1));
                else 
                    ans.insert(pair<int,char>(-1*f,-1));

            }
            int count = 0;
            int sign;
            multimap<int,char>::iterator it = ans.begin();
            if(it->second == 1 ) {
                sign = -1;
                count++;
            }
            else{
                sign = 1;
                count++;
            }
            it++;
            for(;it != ans.end();it++){
                if(it->second == sign){
                    sign = -sign;
                    count++;
                }
            }
            printf("%d\n",count);
        }
    }
    return 0;
}