Description

将1∼n 这 n 个数字首尾相连，形成一个圆环，要求圆环上任意两个相邻的数字之和都是一个素数，请编程输出符合条件的素数环。

Format

Input

输入数据仅一行，包含一个正整数 n（n≤20）。

Output

输出数据最多包括 10 行，每行由 n 个整数组成，表示前十个符合条件的素数环（不足十个时全部输出）。所有素数环第一个元素必须是 1，且按照从小到大的顺序排列。

Samples

4

1 2 3 4
1 4 3 2

Limitation

1s, 1024KiB for each test case.