#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;
}