#include<iostream> 
#include<algorithm>
#include<vector>
#include<bitset>
using namespace std;
int n,ans;
int ls[21];
bool pm[34];

vector<int> mp[16];

inline void dfs(int x,int vis){
	if(x==n+1){
		for(int i=1;i<=n;i++) cout<<ls[i]<<" ";
		cout<<"\n";
		ans++;
	}else{
		for(int i=0;i<mp[ls[x-1]].size();i++){
			int y=mp[ls[x-1]][i];
			if(vis&(1<<y-1)) continue;
			
			ls[x]=y;
							
			dfs(x+1,vis^(1<<y-1));
		}
	}
}

int main(){
    freopen("dfs3.in","r",stdin);
    freopen("dfs3.out","w",stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    pm[2]=pm[3]=pm[5]=pm[7]=pm[11]=pm[13]=pm[17]=pm[19]=pm[23]=pm[29]=pm[31]=1;
    
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(pm[i+j]&&i!=j) mp[i].push_back(j);
    
    for(int i=1;i<=n;i++){
    	ls[1]=i;
    	dfs(2,1<<i-1);
	}
    
    cout<<ans;
    
    return 0;
}