题目描述

奶牛们刚学会原根的定义！给定一个质数 $p$，那么模 $p$ 意义下的一个原根 $x\ (1\le x < p)$ 满足如下性质：$x-1,x^2-1,x^3-1...x^{p-2}-1$ 都不能被 $p$ 整除，但是 $x^{p-1}-1$ 却可以。

但是奶牛们太菜了需要你的帮助，给定一个质数 $p$，求模 $p$ 意义下原根的个数。

输入格式

一个正整数 $p\ (2\le p\le 2000)$，保证其为质数。

输出格式

模 $p$ 意义下原根个数。

3

1

5

2