Untitled

#include<iostream>

using namespace std;

int a[17]={1,-9,2,-9,3,-9,4,-9,5,-9,6,-9,7,-9,8,-9,9};
int T, n, result;

int calcu(){
	int tmp = 1, res = 1, lastValue=1;
	for(int i=0; i<= n-2; i++){
		int t = 2*i+1;
		if(a[t] == 1){
			res+=a[t+1];
			lastValue = a[t+1];
			tmp = 1;
		}
		else if(a[t] == -1){
			res -= a[t+1];
			lastValue = a[t+1];
			tmp = -1;
		}
		else {
			if(tmp==1){
				res = res - lastValue + lastValue*10 + a[t+1];
				lastValue = lastValue*10 + a[t+1];
			}
			else {
				res = res + lastValue - lastValue*10 - a[t+1];
				lastValue = lastValue*10 + a[t+1];
			}
		}
	}
	return res;
}

void solve(int step){
	if(step==n-1){
		if(calcu()==0)
			result++;
		return;
	}
	for(int i=-1; i<2; i++){
		a[2*step+1] = i;
		solve(step+1);
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int tc=1; tc<=T; tc++){
		cin >> n;
		result = 0;
		solve(0);
		cout << "#" << tc << " " << result << endl;
	}
	return 0;
}