# Problem H

Prime Count

Given a positive integer $N$, compute the number of primes less than $N$.

## Input

The first line contains the integer $N$ ($1 \le N \le 10^{11}$).

## Output

Print the number of primes less than $N$.

## Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

Group |
Points |
Constraints |

$1$ |
$1$ |
$N \le 10^6$ |

$2$ |
$1$ |
$N \le 10^7$ |

$3$ |
$1$ |
$N \le 3 \cdot 10^7$ |

$4$ |
$1$ |
$N \le 10^8$ |

$5$ |
$1$ |
$N \le 2 \cdot 10^8$ |

$6$ |
$1$ |
$N \le 10^{9}$ |

$7$ |
$1$ |
$N \le 10^{10}$ |

$8$ |
$1$ |
$N \le 10^{11}$ |

Sample Input 1 | Sample Output 1 |
---|---|

10 |
4 |