http://acm.hdu.edu.cn/showproblem.php?pid=1016
//1276949 2009-04-16 16:47:42 Accepted 1016 484MS 268K 918 B C++ no way 
#include<iostream>
using namespace std;
int n,t;
int prime[38] = {0,0,2,3,0,5,0,7,0,0,0,11,0,13,0,0,0,17,0,19,0,0,0,23,0,0,0,0,0,29,0,31,0,0,0,0,0,37};
bool used[20];//标记i是否用过
int pre_num[20];
void dfs(int v,int num)
{
    int i;
    if(num == n)
    {    
        if(prime[v+1] !=0 )
        {
            cout<<"1";
            for(i=2;i<t;i++)
                cout<<" "<<pre_num[i];
            cout<<endl;
        }
        return ;
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            if(used[i] == false && prime[i+v] != 0 )
            {
                used[i] = true;
                pre_num[t++] = i;
                dfs(i,num+1);
                used[i] = false;
                t--;
            }
        }
    }
}
int main()
{
    int i,cas=1;
    while(cin>>n)
    {
        
        cout<<"Case "<<cas++<<":"<<endl;

        for(i=1;i<=n;i++)
            used[i] = false;
        used[1] = true;
        t = 1;
        pre_num[t++]=1;
        dfs(1,1);

        cout<<endl;
    }
    return 0;
}