描述

我们称整数 $x$（$0 < x < p$）是模奇素数$p$ 的原根，当且仅当集合 $\{ (x^i \mod p) \mid 1 \leq i \leq p-1 \}$ 等于 $\{ 1, \ldots, p-1 \}$。例如，3 模 7 的连续幂次为 3, 2, 6, 4, 5, 1，因此 3 是模 7 的原根。

编写一个程序，给定任意奇素数 $3 \leq p < 65536$，输出模 $p$ 的原根个数。

输入

输入包含若干行，每行一个奇素数 $p$。输入以文件结束符（EOF）终止。

输出

对每个 $p$，在一行中输出模 $p$ 的原根个数。

输入示例

23  
31  
79  

输出示例

10  
8  
24  

来源

贾怡@pku