#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int x[50],k,valid,n,m;
long int nr;

void posibil(int k,int *valid)
{
  int i;
  *valid=1;
for(i=1;i<=k-1;i++)
  if(abs(x[i]-x[k])==abs(i-k)||(x[i]==x[k])) *valid=0;
}
int solutie(int k)
{
  if(k==n)return 1;
  else return 0;
}
void afisare(int k,FILE *g)
{
  int i,j;
  nr++;
  if(nr==1)
    {
  for(i=1;i<=k;i++){
    for ( j=1;j<=k;j++)
      if (x[i]==j)
	fprintf(g,"%d ",j);
  }
    }
}
void backtracking(int k,FILE *g)
{
  //k=1;
  //x[k]=0;
  if(k>0)
    {
      valid=0;
      while(!valid && x[k]<n)
	{
	  x[k]=x[k]+1;
	  posibil(k,&valid);
	}
		if(!valid) backtracking(k-1,g);
		else if(solutie(k)){ afisare(k,g); backtracking(k,g);}
		else {
		  x[k+1]=0;
		  backtracking(k+1,g);
		}
}
}
int main()
{
  FILE *f=fopen("damesah.in","r");
  FILE *g=fopen("damesah.out","w");
  fscanf(f,"%d",&n);
  nr=0;
  x[1]=0;
  backtracking(1,g);
  fprintf(g,"\n%ld",nr);
  fclose(f);
  fclose(g);
  return 0;
}