#描述#
有一种神奇的圆形魔法阵，它上面等间距放有n个球，从任意一个球开始按顺时针将所有的球编号(从1开始)，第i个球自生产生的能量值为i，魔法阵的初始能量为0。
<BR>
<BR>
现在外星人使用了一个特殊的能量吸收器，它会把魔法阵中能力值最大的球的能量变成1，使得圆形魔法阵处于不稳定状态。
<BR>
<BR>
而圆形魔法阵由于有魔法性质，如果在它上面的总球数恰好是质数个的话，它将会经过一个平衡过程重新回到稳定状态，否则魔法阵继续处于不稳定状态，所有的球能量最后都会消失。
<BR>
<BR>
圆形魔法阵的平衡过程如下：
<BR>
1:首先它将所有球的能量吸收，得到的总能量为所有球的能量值之积。
<BR>
2:然后它将能量平均分给所有球(每个球获得的能量必须是整数)
<BR>
3:最后圆形魔法阵自身将可能剩下一些能量(自身能量不包括球的能量)。
<BR>
<BR>
现在，你面对着许多被外星人破坏的不同大小的圆形魔法阵，你能算出每个圆形魔法阵自身最后拥有多少能量吗？(自身能量不包括球的能量)

#格式#
##输入格式##
输入有多组数据,不超过10000组，每组一行，第i行表示第i个圆形魔法阵等间距放有n个球(1 &lt= n &lt= 2000000)。

##输出格式##
针对每个圆形魔法阵，输出它自身最后拥有的能量，每个结果占一行。

#样例1#
##样例输入1##

1
2
2000000

##样例输出1##

0
1
0

#限制#
1000ms
32768KB

#提示#

#来源#