import Data.Set (Set, toList, fromList, findMax, foldl', delete)
main = do
  s <- getContents
  putStr . unlines . map (show . length . primes . read) . lines $ s

primes :: Integer -> [Integer]
primes 1 = []
primes n = toList $ seive 2 $ fromList [2..n]

seive :: Integer -> Set Integer -> Set Integer
seive p xs
  | p*p > findMax xs = xs
  | otherwise        = seive (p+1) $ foldl' (\acc x -> delete x acc) xs (fromList [2*p,3*p..q])
  where q = findMax xs