Untitled

#include<iostream>

using namespace std;
int n;
int a[20];
int x[20];
int ans;

void go(int k)
{
	if(k==n){
		int so=1;
		int sum=0;
		int dau=2;
		x[n]=2;
		for(int i=1;i<=n;i++){
			if(x[i]==0) so=so*10+(i+1);
			else
			{
				if(dau==1) 
				{
					sum-=so;
				}
				else 
				{
					sum+=so;
				}
				dau=x[i];
				so=i+1;
			}
		}
		if(sum==0)ans++;
		return;
	}
	//so lua chon cua candidate
	x[k]=0;go(k+1);
	x[k]=1;go(k+1);
	x[k]=2;go(k+1);
}
int main()
{
	freopen("input.txt","r",stdin);
	int T; cin >> T;
	for(int tc=1;tc<=T;tc++){
		cin >>n;
		
		ans=0;
		go(1);
		cout<<"#"<<tc<<" "<< ans <<endl;
	}
	return 0;
}