# Integer Square Root
# Param::  positive integer n
# Return:: integer part of the square root of n
#  i.e. the number m s.t. m ** 2 <= n < (m + 1) ** 2
def isqrt(n)
	x = 1 << (((n.to_s(2).size - 1) >> 1) + 1)

	loop do
		# Newtonian step
		next_x = (x + n / x) >> 1
		return x if x <= next_x

		x = next_x
	end
end

def eratosthenes_sieve(n)
	return to_enum(:eratosthenes_sieve, n) unless block_given?

	return if n < 2

	yield 2
	return if 2 == n

	yield 3

	# make list for sieve
	sieve_len_max = (n + 1) >> 1
	sieve = [true, false, true]
	sieve_len = 3
	k = 5
	i = 2
	while sieve_len < sieve_len_max
		if sieve[i]
			yield k
			sieve_len *= k
			if sieve_len_max < sieve_len
				sieve_len /= k
				# adjust sieve list length
				sieve *= sieve_len_max / sieve_len
				sieve += sieve[0...(sieve_len_max - sieve.size)]
				sieve_len = sieve_len_max
			else
				sieve *= k
			end

			i.step(sieve_len - 1, k) do |j|
				sieve[j] = false
			end
		end

		k += 2
		i += 1
	end

	# sieve
	limit = (isqrt(n) - 1) >> 1
	while i <= limit
		if sieve[i]
			yield k = (i << 1) + 1
			j = (k ** 2) >> 1
			while j < sieve_len_max
				sieve[j] = false
				j += k
			end
		end

		i += 1
	end

	# output result
	limit = (n - 1) >> 1
	while i <= limit
		yield((i << 1) + 1) if sieve[i]
		i += 1
	end
end

def bisect_right(list, item, lo = 0, hi = list.size)
	while lo < hi
		i = (lo + hi - 1) >> 1

		if 0 < (list[i] <=> item)
			hi = i
		else
			lo = i + 1
		end
	end

	return lo
end

nums = $<.each_line.map(&:to_i)

primes = eratosthenes_sieve(nums.max).to_a
nums.each do |n|
	p bisect_right(primes, n)
end