Problem Description

A logarithm sequence is defined as a sequence of length $n$, denoted as $(a_1, a_2, \ldots, a_n)$, satisfying the condition that for all positive integers $x, y$ such that $\leq n$, we have $a_{xy} = a_x + a_y$. An example of a logarithm sequence of length 6 is $0, 1, \pi, 2, 0.7, 1 + \pi$.

There are $q$ logarithm sequences of length $n$, but each sequence has exactly one element altered. Given the number of sequences $q$, the length of the sequences $n$, and the position $x_i$ of the altered element in each sequence, for each sequence, output the minimum number of elements that need to be modified to make the sequence a logarithm sequence again, without altering the already changed element.

Note: It can be proven that for any initial logarithm sequence, after changing the same position, the minimum number of changes required to transform the sequence back into a logarithm sequence without altering this position is the same.

Input Format

The first line contains two positive integers $n, q\ (1 \leq n \leq 10^8, 1 \leq q \leq 10^4)$, representing the length of the sequences and the number of sequences, respectively.

The next $q$ lines each contain a positive integer $x_i\ (1 \leq x_i \leq n)$, indicating the index of the altered element in the $i$-th sequence.

Output Format

If the $i$-th sequence cannot be transformed into a logarithm sequence without altering the already changed element, output -1. Otherwise, output the minimum number of elements that need to be changed.

Sample Input and Output

Sample Input #1

6 6
1
2
3
4
5
6

Sample Output #1

-1
2
1
2
0
1

Sample Input #2

20 5
7
8
2
19
12

Sample Output #2

1
9
9
0
5

Sample Input #3

10000 4
1234
2345
3456
7890

Sample Output #3

15
148
3332
37

Notes

Explanation of Sample #1:

Assuming the initial sequence is $0, 1, \pi, 2, 0.7, 1 + \pi$, and the fourth element is changed to 8, then the second element can be changed to 4 and the sixth element to $4 + \pi$, resulting in the sequence $0, 4, \pi, 8, 0.7, 4 + \pi$, which is a logarithm sequence again.

见题面 Input 部分

见题面 Output 部分