// Author: Pavel Kuznetsov
//
// Backtracking with optimization and memoization
// Should work not so long for N=30
//
#include <iostream>
#include <map>
#include <stdio.h>
#include <vector>

using namespace std;

#define For(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)

const int MAXN = 40;

int n, can[MAXN+1], mate[MAXN+1];

map <vector<int>,long long> h;

long long solve(int need){
	if (need == 0) return 1LL;
	
	vector <int> v;
	For(i,1,n) v.push_back(can[i]);
	For(i,1,n) if (can[i]==1) v.push_back(mate[i]); else v.push_back(0);
	
	if (h.count(v)) return h[v];
	
	v.clear();
	For(i,1,n) v.push_back(can[n-i+1]);
	For(i,1,n) if (can[n-i+1]==1) v.push_back(n+1-mate[n-i+1]); else v.push_back(0);
		
	if (h.count(v)) return h[v];
	
	long long &res=h[v];
	
	For(i,1,n) if (can[i]) {
		if (i-need > 0 && i-need <= n && mate[i] != i-need && can[i-need]) {
			--can[i]; --can[i-need];
			int m1 = mate[i], m2 = mate[i-need];
			mate[m1] = m2; mate[m2] = m1;
			
			res += solve(need-1);
			
			++can[i]; ++can[i-need];
			mate[m1]=i; mate[m2]=i-need;
		}
	}
	
	return res;
}

int main(){
	
	freopen("output.txt","wt",stdout);
	
	printf("const string res[]={");
	
	For(j,2,30) {
		n=j;
	  For(i,1,n) can[i] = 2, mate[i] = i;
	  cout <<"\""<< 2LL*solve(n-1)<<"\"";
	  if (j!=30) cout <<",";
  }
	
	printf("};");
	
	return 0;
}
