Bò và căn nguyên thuỷ

Cho một số nguyên tố $p$. Một căn nguyên thuỷ modulo $p$ là một số nguyên $x$ với $1\le x<p$ thoả mãn:

• Không tồn tại số nguyên $k$ với $1\le k\le p-2$ sao cho $x^k-1$ chia hết cho $p$.
• $x^{p-1}-1$ chia hết cho $p$.

Cho trước số nguyên tố $p$, hãy đếm số căn nguyên thuỷ modulo $p$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên tố $p$ ($2\le p<2000$).

Dữ liệu ra

In ra một số nguyên duy nhất là số căn nguyên thuỷ modulo $p$.

Ràng buộc

• $p$ là số nguyên tố.
• $2\le p<2000$.

Ví dụ

Ghi chú

Số căn nguyên thuỷ modulo một số nguyên tố $p$ bằng $\phi (p-1)$, trong đó $\phi$ là hàm phi-Euler.