#include <cstdio>
#define N 20
using namespace std;
FILE *F=fopen("damesah.in","r");
FILE *G=fopen("damesah.out","w");

int c[N],d1[N],d2[N],v[N],nr,n;

bool verif(int a)
{
    if( c[ v[a] ] )
        return false;
    if( d1[ N + a - v[a] ] )
        return false;
    if( d2[ a + v[a] ] )
        return false;
    return true;
}
void backtracking(int k){
    int i;
    for(i=1 ; i<=n ; ++i){
        v[k]=i;
        if( verif(k) ){
            if(k == n){
                if(!nr)
                    for(int j=1 ; j<=n ; ++j)
                        if(j==n)
                            fprintf(G,"%d",v[j]);
                        else{
                            fprintf(G,"%d",v[j]);
                            fprintf(G," ");
                        }
                //fprintf(G,"\n");
                //for(int j=1 ; j<=n ; ++j)
                //        fprintf(G,"%d ",v[j]);
                ++nr;
            }
            else{
                c[i]=1;
                d1[N + k - i] = 1;
                d2[k + i] = 1;
                backtracking(k + 1);
                c[i]=0;
                d1[N + k - i] = 0;
                d2[k + i] = 0;
            }
        }
    }
}
int main()
{
    fscanf(F,"%d",&n);
    backtracking(1);
    fprintf(G,"\n");
    fprintf(G,"%d",nr);
    fprintf(G,"\n");
    return 0;
}