#include <iostream>
#include <fstream>
#include <vector>

std::ifstream f("damesah.in");
std::ofstream g("damesah.out");

bool isFirstSolution;
int n,cnt;
std::vector<int>cols;

bool isOk(int k){
    
    for(int i = 0;i < k;++i){
        
        if(cols[i] == cols[k])
            return false;
        if(abs(k - i) == abs(cols[k] - cols[i]))
            return false;
    }
    
    return true;
    
}

void printSol(){
    
    if(isFirstSolution){
        for(int i = 0;i < n;++i)
            g << cols[i] << ' ';
        g << '\n';
        isFirstSolution = false;
        cnt = 1;
    }else cnt++;
}

void back(int k){
    
    for(int i = 0;i < n;++i){
        
        cols[k] = i;
        
        if(isOk(k)){
            
            if(k == n - 1)
                printSol();
            else
                back(k + 1);
        }
        
    }
    
}

int main(){
    
    std::cin >> n;
    cols.resize(n);
    
    back(0);
    g << cnt;
    
    return 0;
}