Problem Description

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

There are $q$ logarithmic sequences of length $n$, but now in each sequence exactly one element has been changed. You are given the number of sequences $q$, the sequence length $n$, and the position $x_i$ of the changed element in each sequence. For each sequence, output the minimum number of positions that must be modified so that the sequence is still a logarithmic sequence, under the condition that the already changed element must not be modified.

Note: It can be proven that for any initial logarithmic sequence, after changing the same position, the minimum number of modifications needed to turn the sequence back into a logarithmic sequence (without modifying that position) is always the same.

Input Format

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

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

Output Format

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

6 6
1
2
3
4
5
6

-1
2
1
2
0
1

20 5
7
8
2
19
12

1
9
9
0
5

10000 4
1234
2345
3456
7890

15
148
3332
37

Hint

Explanation for Sample $1$:

Assume the initial sequence is $0,1,\pi,2,0.7,1+\pi$. If the fourth element is changed to $8$, then we can change the second element to $4$ and the sixth element to $4+\pi$. The sequence becomes $0,4,\pi,8,0.7,4+\pi$, which is a logarithmic sequence again.

Translated by ChatGPT 5