lst=[true]*999999
lst2=[]
lst[0]=false
lst[1]=false
for i in (2..999999)
	if lst[i] == true
		(i+i).step(999999,i){|j|
			lst[j] = false
		}
		lst2.push i
		lst[i]=lst2.size
	end
end
p lst.count true
p lst2.size
n = $<.each_line.map &:to_i
for k in n
	puts lst[k]
end