10000 - Fade

通过次数

115

提交次数

145

时间限制 : 1 秒
内存限制 : 512 MB

音乐链接

——Alan Walker 《Fade》

wlxsq觉得开场应该放一道签到题,所以您可以尽情放着《Fade》做此题。

给你一个质数p,求有多少个正整数x,满足x<p 并且 x^2\ mod\ p=1

注意:mod是取模的意思,比如5\ mod\ 3 =2, 4\mod\ 2 = 0

输入

输入一个质数p

输出

输出满足条件的正整数x的个数。

样例

输入

7

输出

2

输入

5

输出

2

提示

样例解释

对于第一组数据,有x=1x=6满足条件;

对于第二组数据,有x=1x=5满足条件。

数据范围

对于100%的数据,1\le p\le 1000