#include <iostream>
#include <fstream>

const int MAXN = 30;
const int dx[] = {-1,-1,-1,0,1,1,1,0};
const int dy[] = {-1,0,1,1,1,0,-1,-1};

using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

int n,cnt;
bool matrice[MAXN][MAXN];
bool linie[MAXN],coloana[MAXN],diag1[MAXN],diag2[MAXN];

bool validare(int x,int y){
    if(linie[x] || coloana[y] || diag1[x - y] || diag2[x + y])
        return false;
    for(int i = 0 ; i < 8; ++i){
        int xnou = x + dx[i];
        int ynou = y + dy[i];
        while(1 <= xnou && xnou <= n && 1 <= ynou && ynou <= n){
            if(matrice[xnou][ynou])
                return false;
            xnou += dx[i];
            ynou += dy[i];
        }
    }
    return true;
}
void afis(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            cout<<matrice[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl<<"========="<<endl;
}
void backtracking(int k){
    if(k == n + 1){
        if(cnt == 0){
            for(int i = 1; i <= n; ++i){
                int j;
                for(j = 1; j <= n && !matrice[i][j]; ++j);
                out<<j<<" ";
            }
            out<<"\n";

        }
        cnt++;
    }


    for(int j = 1; j <= n; ++j){
        if(validare(k,j)){
            afis();
            matrice[k][j] = true;
            linie[k] = true;
            coloana[j] = true;
            diag1[j - k + n] = true;
            diag2[j + k] = true;
            backtracking(k + 1);
            matrice[k][j] = false;
            diag1[j - k + n] = false;
            diag2[j + k] = false;
            linie[k] = false;
            coloana[j] = false;
        }
    }

}

int main()
{
    in.tie(NULL);
    out.tie(NULL);
    ios::sync_with_stdio(false);
    in>>n;
    backtracking(1);
    out<<cnt;
    return 0;
}