Untitled

#include<iostream>
using namespace std;
int n;
int cnt;
void backtrack(int k,long long count){
	if(k==n+1){
		 if(count==0) cnt++;
		return;
	}
	long long temp = 0;
	for(int i =k;i<=n;i++){
		temp = temp*10+i;
		backtrack(i+1,count + temp);
		backtrack(i+1,count - temp);
	}
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	ios::sync_with_stdio(false);
//	freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin >> n;
		cnt=0;
		backtrack(1,0);
		cout << "#" << test_case << " " << cnt/2 << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}