#include
using namespace std;
bool canplace(char board[][100],int i,int j,int n)
{
if((i-1)>=0 && (j-2)>=0 && board[i-1][j-2]==‘K’)
return false;
if((i-2)>=0 && (j-1)>=0 && board[i-2][j-1]==‘K’)
return false;
if((i-1)>=0 && (j+2)<n && board[i-1][j+2]==‘K’)
return false;
if((i-2)>=0 && (j+1)<n && board[i-2][j+1]==‘K’)
return false;
if(board[i][j]==‘K’)
return false;
return true;
}
int ans=0;
bool solvenknight(char board[100][100],int n,int i,int j,int placed)
{
if(j==n)
return solvenknight(board,n,i+1,0,placed);
if(placed==n)
{
ans++;
for(int x=0;x<n;x++){
for(int y=0;y<n;y++){
{
if(board[x][y]==‘K’)
cout<<"{"<<x<<"-"<<y<<"} ";
}
        }
    }cout<<" ";
    return true;
}
for(int x=i;x<n;x++)
{
    for(int y=j;y<n;y++)
    {
        if(canplace(board,x,y,n))
        {
            board[x][y]='K';
            placed++;
            solvenknight(board,n,x,y+1,placed);
            placed--;
        }
        board[x][y]='_';
    }
}
for(int x=i+1;x<n;x++)
{
    for(int y=0;y<j;y++)
    {
       if(canplace(board,x,y,n))
        {
            board[x][y]='K';
            placed++;
            solvenknight(board,n,x,y+1,placed);
            placed--;
        }
        board[x][y]='_';
    }
}
}
int main(){
char board[100][100];
int n;
cin>>n;
for(int x=0;x<n;x++){
        for(int y=0;y<n;y++){
            board[x][y]='_';
        }
    }
solvenknight(board,n,0,0,0);
cout<<endl<<ans;
return 0;
}
 
      
    