Solution:

#include
#include

using namespace std;
#define max_num 16
#define READ(f) freopen(f,"r",stdin)

int dataArray[max_num];
int output[max_num];
bool visited[max_num];
int N;
int TEST_CASE;
int PRINT_FLAG; int PRINT_NEWLINE;

void generatePermutation(int level, int taken);
void printPermutation();
void init();
bool checkPrime(int num);


int main()
{
    N = 0,TEST_CASE = 0, PRINT_NEWLINE = 0;
    READ("524.txt");
    while (!cin.eof())
    {
        TEST_CASE++;
        PRINT_FLAG = TEST_CASE;

        cin >> N;
        for (int i = 1; i <= N; i++)
        {
            dataArray[i - 1] = i;
        }

        generatePermutation(0, N);
        PRINT_NEWLINE = 1;
    }

    return 0;
}

void generatePermutation(int level, int taken)
{
    if (level == taken)
    {
        if (output[0] == 1) // As decribed in the question that "the number of first circle should always be 1."
            printPermutation();
        return;
    }

    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            output[level] = dataArray[i];
            generatePermutation(level + 1, taken);
            visited[i] = false;
        }
    }
}

void printPermutation()
{
    bool isPrime = false;


    for (int j = 0; j <= N-1; j++)
    {
        if (j < N - 1)
            isPrime = checkPrime(output[j] + output[j + 1]);
        else
            isPrime = checkPrime(output[j] + output[0]);
        if (!isPrime) break;
    }

    if (isPrime){

        if (PRINT_NEWLINE)
            cout << endl;

        if (PRINT_FLAG == TEST_CASE)
        {
            cout << "Case " << TEST_CASE << ":" << endl;
            PRINT_FLAG++;
            PRINT_NEWLINE = 0;
        }

        for (int i = 0; i < N; i++)
        {
            cout << output[i] << " ";
        }

        cout << endl;
    }
}

void init()
{
    for (int i = 0; i < max_num; i++)
    {
        visited[i] = false;
    }
}

bool checkPrime(int num)
{
    if (num == 2) return true;
    for (int i = 2; i < num / 2; i++)
    {
        if (num % i == 0) return false;
    }

    return true;
}