学步园

/*

          题目大意：跟上一道POJ棋盘题目一样，不过需要判断不能为对角线的情况

*/


#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int res[12];     //保存需要的输出结果 
int visi[12];   //每一列被访问的情况
int ma[12];     //用来存储皇后的位置，以免在同一个对角线上
int sum,l;

void dfs(int row,int pos)
{
    if(pos==l)
	{
	   sum++;
	   return;
	}
	if(row>l)
		return;
	for(int j=1;j<=l;j++)
		if(!visi[j])
		{
			int flag=0;
			ma[row]=j;

			for(int k=1;k<row;k++)
				if(abs(ma[k]-ma[row])==abs(row-k))      
				{
				   flag=1;
				   break;
				}
			if(!flag)
			{
		      visi[j]=1;
			  dfs(row+1,pos+1);
			  visi[j]=0;
			}
		}
    dfs(row+1,pos);
    return ;
}

int main()
{
   for(l=1;l<=10;l++)
   {
       memset(visi,0,sizeof(visi));
	   sum=0;
	   dfs(1,0);
	   res[l]=sum;
   }

   int p;
   while(cin>>p&&p)
   {
      cout<<res[p]<<endl;
   }
   return 0;
}