Untitled

#include<iostream>
using namespace std;
int TC, N, co;
void doing(int k, int s, int c, int tmp, int prec) {
	int ns = s, ntmp = 0, nprec = prec;
	if(c == 0) ntmp = tmp * 10 + k + 1;
	else ns = s + prec * tmp, ntmp = k + 1;
	if(k + 1 == N) {
		if((c == 0 && ns + prec * ntmp == 0) || (c != 0 && ns + c * ntmp == 0)) co++;
	} else {
		if(c != 0) nprec = c;
		doing(k + 1, ns, 0, ntmp, nprec);
		doing(k + 1, ns, 1, ntmp, nprec);
		doing(k + 1, ns, -1, ntmp, nprec);
	}
}
int main() {
	cin >> TC;
	for(int tc = 1; tc <= TC; tc++) {
		cin >> N;
		co = 0;
		doing(0, 0, 0, 0, 1);
		cout << "#" << tc << " " << co << endl;
	}
	return 0;
}