题目描述

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

输入格式

多组用例，每组用例一行，包含一个正整数，表示$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