24503번 - 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)$

노트