奶牛们刚刚学会了什么是原根!给定素数 p,原根 $$\bmod p$$ 是一个整数 x (1 ≤ x < p),使得整数 x - 1、x2 - 1、...、xp - 2 - 1 都不能被 p 整除,但 xp - 1 - 1 可以。
不幸的是,计算原根可能非常耗时,因此奶牛需要您的帮助。给定一个素数 p,帮助奶牛找到原根 $$\bmod p$$ 的数量。
输入
输入包含一行,其中包含整数 p (2 ≤ p < 2000)。保证p是素数。
输出
在单行上输出原根 $$\bmod p$$ 的数量。
示例
输入 #1
3
输出 #1
1
输入 #2
5
输出 #2
2
注意
唯一的原根 $$\bmod 3$$ 是 2。
原根 $$\bmod 5$$ 是 2 和 3。