You have an array A of length N. You can perform an operation (you can perform the operation multiple times) on the elements of the array A. In the operation you can divide any element by its smallest factor greater than 1. You will be given Q tasks. In each task, you will be given an integer K and you have to tell the maximum number of elements in array A that can be reduced to 1 by using the operation at most K times.

Constraints:
\(1 \le N \le 10^6\)
\(1 \le Q \le 10^5\)
\(1 \le A_i \le 10^6\)
\(1 \le K \le 10^6\)

Input:
First line contains two space separated integers, N and Q.
Second line contains N space separated integers denoting the elements of the array A.
Next Q lines contains an integer each, denoting the value of K.

Output:
For each task, print the answer of the \(i^{th}\) task in a new line.