#include<iostream>#include<cstring>#include<cstdio>#include<string>#include<algorithm>#define ll long long#define maxn 1205#define eps 1e-8using namespace std;int a[4][4];ll v[17];int *t1,*t2,*prod;bool ok(int depth){ int x=depth/4,y=depth%4; for(int i=0;i<y;++i) if(a[x][i]==a[x][y])return 0; for(int i=0;i<x;++i) if(a[i][y]==a[x][y])return 0; return 1;}void dfs(int depth,int kind){ if(depth==16){v[kind]++; return;} int x=depth/4,y=depth%4; for(int i=1;i<=kind;++i){ a[x][y]=i; if(ok(depth)) dfs(depth+1,kind); } a[x][y]=kind+1; dfs(depth+1,kind+1);}int* str2int(char* str){ int i,len=strlen(str); int* a=new int[(len+1)*sizeof(int)]; for(i=0;i<len;++i)a[i]=(int)str[len-i-1]-48; return a;}char* int2str(int *a,int n){ char *str=new char[(n+1)*sizeof(char)]; for(int i=0;i<n;++i) str[i]=(char)a[n-i-1]+48; str[n]=' '; return str;}int check(int* a,int n){ int k=0,len=n; while(a[len-1]==0&&len>1)len--; for(k=0;k<len;++k) if(a[k]>=10) a[k+1]+=a[k]/10, a[k]%=10; if(a[k]!=0)len=k+1; return len;}char* addition(char* m1,char* m2){ int i,j,len1,len2,len,c=0; len1=strlen(m1),len2=strlen(m2); len=max(len1,len2); t1=str2int(m1),t2=str2int(m2); for(i=len1;i<len+1;++i)t1[i]=0; for(i=len2;i<len+1;++i)t2[i]=0; for(i=0;i<len;++i) t1[i]+=t2[i]; delete []t2; len=check(t1,len); return int2str(t1,len);}char* multiply(char* m1,char* m2){ int i,j,len1,len2,len,c=0; len1=strlen(m1),len2=strlen(m2); len=len1+len2; prod=new int[(len+1)*sizeof(int)]; t1=str2int(m1),t2=str2int(m2); for(i=0;i<len+1;++i)prod[i]=0; for(i=0;i<len1;++i) for(j=0;j<len2;++j)prod[i+j]+=t1[i]*t2[j]; len=check(prod,len); delete []t1; delete []t2; return int2str(prod,len);}int u[maxn],tail;void work(ll n){ tail=0; while(n)u[tail++]=n%10,n/=10;}int main(){ for(int i=0;i<4;++i) a[0][i]=i+1; memset(v,0,sizeof(v)); dfs(4,4); int T; ll n; cin>>T; char *p,*pp,*ans,*t; for(int kase=1;kase<=T;++kase){ cin>>n; if(n<4){cout<<0<<endl; continue;} for(ll i=4;i<=min(16LL,n);++i){ work(v[i]); t=int2str(u,tail); for(int j=0;j<i;++j){ work(n-j); p=int2str(u,tail); pp=t; t=multiply(t,p); delete []prod; delete []p; delete []pp; } if(i==4)ans=t; else{ p=ans; pp=t; ans=addition(ans,t); delete []t1; delete []p; delete []pp; } } p=ans; ans=multiply(ans,ans); delete []prod; delete []p; p=ans; ans=multiply(ans,ans); delete []prod; delete []p; cout<<ans<<endl; delete []ans; } return 0;}
