Description

露娜同学有一个小秘密，其实她是素数奥特曼的人间体，变身时需要借助“素数环”的力量。素数环带有有1到N，N个数字徽章。将这些数字徽章插入变身器成一个环，使得相邻两个徽章上的数字和为一个素数，就能变身成素数奥特曼。根据徽章的排布方式不同，就能变身成不同形态的素数奥特曼。

请你编写一个程序，计算露娜同学能变身成几种形态的奥特曼？如果不能变身，说明露娜同学撒了谎，请输出“Lie！”。

Input

1行，一个整数n，表示数字徽章的个数（N<18）

Output

如果可以变身，输出所有变身方案，一行一个方案，最后输出方案总数。

如果不可以变身，输出“Lie！”。

Samples

8

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
4