Description

Give you a lot of positive integers, just to find out how many prime numbers there are.

Format

Input

There are a lot of cases.
In each case, there is an integer $N$ representing the number of integers to find.
Each integer won’t exceed 64-bit signed integer, and each of them won’t be less than 2.

Output

For each case, print the number of prime numbers you have found out.

Samples

3
2 3 4

2