#include <bits/stdc++.h>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n;
int poz[10][13]=
{
{2, 4, 1, 3, 0, 0, 0, 0,0,0, 0, 0,0},
{1, 3, 5, 2, 4, 0, 0, 0,0,0, 0, 0,0},
{1, 3, 5, 2, 4, 0, 0, 0,0,0, 0, 0,0},
{1, 3, 5, 7, 2, 4, 6, 0,0,0, 0, 0,0},
{1, 5, 8, 6, 3, 7, 2, 4,0,0, 0, 0,0},
{1, 3, 6, 8, 2, 4, 9, 7,5,0, 0, 0,0},
{1, 3, 6, 8,10, 5, 9, 2,4,7, 0, 0,0},
{1, 3, 5, 7, 9,11, 2, 4,6,8,10, 0,0},
{1, 3, 5, 8,10,12, 6,11,2,7, 9, 4,0},
{1, 3, 5, 2, 9,12,10,13,4,6, 8,11,7},
};
int Nr[10]={2,10,4,40,92,352,724,2680,14200,73712};

int main()
{
    f>>n;
    for(int i=0;i<n;i++)
    g<<poz[n-4][i]<<' ';
    g<<'\n'<<Nr[n-4]<<'\n';
    return 0;
}