OpenKattis
Extrauppgifter [converted from problem group]

Start

2020-03-18 16:00 AKDT

Extrauppgifter [converted from problem group]

End

2021-03-18 16:00 AKDT
The end is near!
Session is over.
Not yet started.
Session is starting in -257 days 11:56:14

Time elapsed

6179:56:14

Time remaining

2580:03:46

Problem H
Prime Sieve

Input

The first line of input consists of two integers $n$, $q$, where $1 \leq n \leq 10^8$ and $1 \leq q \leq 20000$. Then follow $q$ lines, each containing an integer $x$ satisfying $1 \leq x \leq n$.

Output

On the first line of output, write one line giving the number of prime numbers less than or equal to $n$. Then for each query $x$, output $1$ if $x$ is a prime and ouput $0$ if $x$ is composite.

Sample Input 1 Sample Output 1
9973 6
1
2
3
4
9972
9973
1229
0
1
1
0
0
1