[AHOI2007]密码箱

在一次偶然的情况下，小可可得到了一个密码箱。听说里面藏着一份古代流传下来的藏宝图，只要能破解密码就能打开箱子，而箱子背面刻着的古代图标，就是对密码的提示。

经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数与密码的关系。假设这个数是 $n$，密码为 $x$，则密码满足以下条件：

• $x\ge 0$ 且 $x<n$；
• $x^2$ 除以 $n$ 的余数为 $1$。

小可可知道，满足上述条件的 $x$ 可能不止一个，因此需要找出所有满足条件的 $x$，密码一定在其中。请编写程序帮助小可可完成计算。题中 $x$、$n$ 均为正整数。

输入格式

输入文件只有一行，包含一个整数 $n$，满足 $1\le n\le 2\times 10^9$。

输出格式

如果不存在满足条件的 $x$，输出一行 None。

否则，请按照从小到大的顺序输出所有满足条件的 $x$，每行输出一个数。

样例输入

12

样例输出

1
5
7
11

数据范围

• $1\le n\le 2\times 10^9$。

来源与许可

本题为 AHOI 2007 试题「密码箱」，题面与测试数据整理自 BZOJ 1406。

样例 1

输入

12

输出

1
5
7
11