#include #include #include #include using namespace std; long long readInt(long long l,long long r,char endd){ long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true){ char g=getchar(); if(g=='-'){ assert(fi==-1); is_neg=true; continue; } if('0'<=g && g<='9'){ x*=10; x+=g-'0'; if(cnt==0){ fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd){ assert(cnt>0); if(is_neg){ x= -x; } assert(l<=x && x<=r); return x; } else { assert(false); } } } string readString(int l,int r,char endd){ string ret=""; int cnt=0; while(true){ char g=getchar(); assert(g!=-1); if(g==endd){ break; } cnt++; ret+=g; } assert(l<=cnt && cnt<=r); return ret; } long long readIntSp(long long l,long long r){ return readInt(l,r,' '); } long long readIntLn(long long l,long long r){ return readInt(l,r,'\n'); } string readStringLn(int l,int r){ return readString(l,r,'\n'); } string readStringSp(int l,int r){ return readString(l,r,' '); } int T; int n; int r0,r1,r2,r3; bool dp[2][311][311][311][4]; bool vis[2][311][311][311][4]; void search(int i,int j,int k,int l,int p){ if(vis[i][j][k][l][p])return; vis[i][j][k][l][p]=true; dp[i][j][k][l][p]=false; if(i>0 && !vis[i-1][j][k][l][p]){ search(i-1,j,k,l,p); } if(j>0 && !vis[i][j-1][k][l][(p+1)%4] && (p+1)% 4 != 2 ){ search(i,j-1,k,l,(p+1)%4); } if(k>0 && !vis[i][j][k-1][l][(p+2)%4] && (p+2)%4 != 2){ search(i,j,k-1,l,(p+2)%4); } if(l>0 && !vis[i][j][k][l-1][(p+3)%4] && (p+3)%4 != 2){ search(i,j,k,l-1,(p+3)%4); } if(i>0 && !dp[i-1][j][k][l][p]){ dp[i][j][k][l][p]=true; } if(j>0 && !dp[i][j-1][k][l][(p+1)%4] && (p+1)% 4 != 2 ){ dp[i][j][k][l][p]=true; } if(k>0 && !dp[i][j][k-1][l][(p+2)%4] && (p+2)%4 != 2){ dp[i][j][k][l][p]=true; } if(l>0 && !dp[i][j][k][l-1][(p+3)%4] && (p+3)%4 != 2){ dp[i][j][k][l][p]=true; } } int main(){ T=readIntLn(1,10); while(T--){ n=readIntLn(1,300); r0=r1=r2=r3=0; for(int i=0;i