Fixing a Logarithmic Sequence

A sequence \( (a_1, a_2, \ldots, a_n) \) of length \( n \) is called a logarithmic sequence if it satisfies the following property: for all positive integers \( x, y \) with \( xy \le n \) we have

For example, one logarithmic sequence of length \( 6 \) is given by

(0,\ 1,\ \pi,\ 2,\ 0.7,\ 1+\pi).

Now, you are given (q) sequences of length ( n ). In each sequence exactly one element has been modified; its index is given by (x_i) (1-indexed). The modified element is fixed and you are not allowed to change it. For every sequence, determine the minimum number of other positions that you must modify so that the sequence can be turned into a logarithmic sequence (i.e. there exists a sequence ( (c_1,c_2,\ldots,c_n) ) satisfying ( c_{xy}=c_x+c_y ) for all ( x,y ) with ( xy\le n ) and ( c_{x_i}=b_{x_i} ) for the changed index).

Note: It can be proven that for any initial logarithmic sequence, the minimum number of modifications (not counting the already changed element) required to make it a logarithmic sequence is the same regardless of the original logarithmic sequence chosen.

Observation: If the original logarithmic sequence is given by some function \(f\) such that \(a_i=f(i)\) and one element at index \(k\) is altered (i.e. \(b_k\neq a_k\)), then if we try to restore the logarithmic property by adjusting the "free parameters" (the values of \(f(p)\) for prime \(p\)), one may adjust a single prime divisor \(p\) of \(k\) by an offset \(d=b_k-a_k\). Such an adjustment will affect all positions divisible by \(p\). The number of indices (other than \(k\)) which are multiples of \(p\) is \(\lfloor n/p\rfloor-1\). Therefore, the answer is the minimum over all prime divisors \(p\) of \(k\):

You are given \(q\) and \( n \) and then \(q\) lines each containing an integer \( x_i \) (assume \( x_i\ge2 \) so that there is at least one prime divisor). For each query, output the minimum number of changes required (other than the changed element) so that the sequence can be made into a logarithmic sequence.

inputFormat

The first line contains two integers \(q\) and \(n\) (number of sequences and length of each sequence).

Then \(q\) lines follow, each containing a single integer \( x_i \) denoting the position of the element that was modified in that sequence.

outputFormat

For each sequence, output a single integer: the minimum number of positions (other than the already changed index) that must be modified to turn the sequence into a logarithmic sequence.

sample

3 6
2
3
5

2
1
0