G. The Totient Challenge
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this challenge, $$$n$$$ players are arranged in a line with positions numbered from $$$1$$$ to $$$n$$$. The goal of the challenge is simple: only a few players will survive, and the rest will be eliminated based on their position and a mathematical property known as Euler's Totient Function.

After the players are arranged, a guard will go through each position and determine whether the player in that position should be eliminated or not. The decision to eliminate a player depends on a mathematical condition involving Euler's Totient Function, $$$\varphi(k)$$$, which is defined as the number of integers from $$$1$$$ to $$$k$$$ that are coprime with $$$k$$$. To make the decision, the guard will check each position $$$k$$$ $$$(1 \leq k \leq n)$$$ and ask, does $$$\varphi(k)$$$ divide $$$k$$$? If yes, the player survives; otherwise, the player in that position will be eliminated.

Your task is to determine how many players will survive.

Input

A single integer $$$n$$$ $$$(1 \leq n \leq 10^{18} )$$$ — number of players.

Output

Output a single integer representing the number of survivors.

Examples
Input
6
Output
4
Input
1000000
Output
130
Note

Euler's totient function, denoted as $$$ \varphi(n) $$$, counts the number of positive integers from $$$ 1 $$$ to $$$ n $$$ that are coprime to $$$ n $$$, meaning they do not share any common divisor with $$$ n $$$ other than $$$ 1 $$$.

The function satisfies the following formula for any positive integer $$$ n $$$ with prime factorization:

$$$$$$ n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k} $$$$$$

where $$$ p_1, p_2, \dots, p_k $$$ are distinct prime numbers. The totient function is given by:

$$$$$$ \varphi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \dots \left( 1 - \frac{1}{p_k} \right) $$$$$$

For a prime number $$$ p $$$, we have:

$$$$$$ \varphi(p) = p - 1 $$$$$$

since all numbers less than $$$p $$$ are coprime to it.

test case 1

  • $$$\varphi(1)=1$$$ because only the number $$$1$$$ is coprime with itself.
  • $$$\varphi(2)=1$$$ because only the number $$$1$$$ is coprime to $$$2$$$.
  • $$$\varphi(3)=2$$$ because only the numbers $$$1$$$ and $$$2$$$ are coprime to $$$3$$$.
  • $$$\varphi(4)=2$$$ because only the numbers $$$1$$$ and $$$3$$$ are coprime to $$$3$$$.
  • $$$\varphi(5)=4$$$ because only the numbers $$$1$$$ and $$$2$$$ are coprime to $$$3$$$.
  • $$$\varphi(6)=2$$$ because only the numbers $$$1$$$ and $$$5$$$ are coprime to $$$6$$$.
So only players in positions $$$1,2,4$$$ and $$$6$$$ are the survivors