Write a program which reads an integer *n* and prints the number of prime numbers which are less than or equal to *n*. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5, 7.

Input consists of several datasets. Each dataset has an integer *n* (*n* ≤ 999999) in a line.

The number of datasets ≤ 30.

For each dataset, prints the number of prime numbers.

10 3 11

4 2 5

Source: PC Koshien 2003
, All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2003

http://www.pref.fukushima.jp/pc-concours/

http://www.pref.fukushima.jp/pc-concours/