Number Theory#1564

Number Theory

1 second

128 megabytes

Very easy

For the given positive integer $n$ , find the number of integers $m$ such that $1 \leq m \leq n$ 1 \le m \le n, $g cd (m, n) \neq = 1$ \gcd(m, n) \ne 1, and $g cd (m, n) \neq = m$ \gcd(m, n) \ne m. Here, $g cd$ stands for "greatest common divisor".

Input

Each line contains one positive integer $n$ ( $0 < n < 2^{31}$ 0 < n < 2^{31}).

Output

For each $n$ , output the number of integers $m$ that satisfy the conditions, one per line.

Examples

Example 1

Loading

1 \leq m \leq n

g cd (m, n) \neq = 1

g cd (m, n) \neq = m

0 < n < 2^{31}