#include <fstream>
#include <cmath>

using namespace std;

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

const int Nmax = 15;
const int NMAX = 30;
int queen[Nmax],nr_of_solution,n;
bool col[NMAX],dgp[NMAX],dgs[NMAX];
bool printed;

void make(int k){
    int i;
    for(i = 1 ; i <= n ; i++){
        if(!col[i] && !dgp[n + i - k] && !dgs[i + k - 1]){
            queen[k] = i;
            col[i] = dgp[n + i - k] = dgs[i + k - 1] = 1;
            if(k == n){
                nr_of_solution++;
                if(!printed){
                        int x;
                        for(x = 1 ; x <= n ; x++)
                            g << queen[x] << " ";
                        g << "\n";
                        printed = 1;
                }

            }else{
                make(k + 1);
            }
             col[i] = dgp[n + i - k] = dgs[i + k - 1] = 0;
        }
    }
}

int main(){
    f >> n;
    make(1);
    g << nr_of_solution ;

return 0;
}