← 返回题目列表

Codeforces · 284/A

A. 牛和原始根源

中文机器翻译题面 查看原题

奶牛们刚刚学会了什么是原根!给定素数 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。