blobfearful

건우는 다음과 같은 문제를 만들었다.

연구소에 동거하는 채완이와 주환이는 블롭을 아주 좋아한다.

그래서 둘은 블롭을 연구소로 데려와 키운다. 그런데, 키우는 것만으로는 모자란 나머지, 약을 만들어 블롭의 수를 늘리기로 했다.

이 약은 시간이 지날수록 효과가 좋아져 $i$일에는 블롭의 수가 전날의 $i$배가 된다. $1$일에는 블롭 한 마리가 있고, $2$일부터 약을 사용하기로 했다.

그러나, 급격하게 늘어난 개체수로 인해 블롭의 수가 $K$의 배수가 아니라면 블롭들이 불안해한다.

그래서 주환이는 처음으로 블롭들이 불안해하지 않는 날에 약의 사용을 멈추기로 했다.

블롭의 수가 처음으로 $K$의 배수가 되는 날을 구하여라.

그러나, 문제가 너무 쉬워 보여 질의를 주기로 했다.

$Q$ 개의 정수 $A\_i$에 대하여 $1$일에 블롭 한 마리 대신, $A\_i$마리가 있을 때 문제의 정답을 각각 출력하자.

첫째 줄에 정수 $K$와 질의의 개수 $Q$가 공백으로 구분되어 주어진다.

둘째 줄에 질의의 정보 $A\_1, A\_2, \cdots, A\_Q$가 공백으로 구분되어 주어진다.

각 질의마다 문제의 정답을 한 줄에 공백으로 구분하여 순서대로 출력한다.

• $2 \le K \le 10^{15}$
• $1 \le Q \le 10^5$
• $1 \le A\_q < K$ $(1 \le q \le Q)$