1. 
/** * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* * Problem: 524 Prime Ring Problem
* * Link: http://uva.onlinejudge.org/external/5/524.pdf
* * @author Savkina Ekaterina
* * @version 1.0, 08/06/2010
* * Method : Ad-Hoc
* * Status : Accepted
* * Runtime: 0.840 */
import java.util.Scanner;

public class Ring {
private static int N;
private static StringBuffer output = new StringBuffer();

private int[] is_prime = { 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0,
0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1,
0, 0 };

private char v[];
private int ring[];

public void dfs(int n, int d) {
int i;

if (d != 1) {
if (is_prime[n + ring[d - 1]] == 0)
return;
}
v[n] = 1;
ring[d] = n;

if (d == N) {
if (is_prime[n + ring[1]] == 1) {
output.append(ring[1]);

for (i = 2; i <= N; i++)
output.append(" " + ring[i]);
output.append("\n");

}
} else {
for (i = 1; i <= N; i++) {
if (v[i] != 1)
dfs(i, d + 1);
}
}

v[n] = 0;
}

public Ring() {
v = new char[N + 1];
ring = new int[N + 1];
}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int count = 1;
while (sc.hasNext()) {
N = sc.nextInt();
output = new StringBuffer();
Ring p = new Ring();

output.append("Case " + count + ":\n");

count++;
if (N == 1)
output.append("1");
else {

p.dfs(1, 1);
}
if (sc.hasNext()) {
output.append("\n");
}

System.out.print(output);
}

}
}