Description

有一种神奇的圆形魔法阵，它上面等间距放有n个球，从任意一个球开始按顺时针将所有的球编号(从1开始)，第i个球自生产生的能量值为i，魔法阵的初始能量为0。

现在外星人使用了一个特殊的能量吸收器，它会把魔法阵中能力值最大的球的能量变成1，使得圆形魔法阵处于不稳定状态。

而圆形魔法阵由于有魔法性质，如果在它上面的总球数恰好是质数个的话，它将会经过一个平衡过程重新回到稳定状态，否则魔法阵继续处于不稳定状态，所有的球能量最后都会消失。

圆形魔法阵的平衡过程如下：

1:首先它将所有球的能量吸收，得到的总能量为所有球的能量值之积。

2:然后它将能量平均分给所有球(每个球获得的能量必须是整数)

3:最后圆形魔法阵自身将可能剩下一些能量(自身能量不包括球的能量)。

现在，你面对着许多被外星人破坏的不同大小的圆形魔法阵，你能算出每个圆形魔法阵自身最后拥有多少能量吗？(自身能量不包括球的能量)

Input

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

Output

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

Sample

Input

1
2
2000000

Output

0
1
0