题目描述

输入正整数 $n$，把整数 $1,2,\dots,n$ 组成一个环，使得相邻两个整数之和均为素数。同一个环恰好输出一次。$1 \le n \le 16$，保证一定有解。

注意环的输出方式要求：每种排列方法都从 1 开始输出（即固定起点为 1），不同的排列方法按字典序从小到大输出。

输入格式

多组用例，每组用例一行，包含一个正整数，表示 $n$ 的大小。

输出格式

第 $i$ 组数据输出前加上一行 Case i:，后面跟若干行，每行一种排列方式（从 1 开始）。相邻两组输出之间加入一个空行。

每行排列中数字之间用一个空格分隔，排列最后可以带或不带末尾空格，但请保持与样例格式一致。

输入样例 #1

6
8

输出样例 #1

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2