import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
sys.setrecursionlimit(10**7)
yes = lambda :print("yes");Yes = lambda :print("Yes")
no = lambda :print("no");No = lambda :print("No")
inf = 10**16
#######################################################################
k, q = na()

from bisect import *
bl = bisect_left
br = bisect_right


def f(n):
    r = 0
    while True:
        #print(n)
        if n%k==0:
            break
        n = n-(n+k-1)//k
        r+=1
    return r

def g(n):
    r = []
    while n>0:
        r.append(str(n%k))
        n//=k
    return "".join(r[::-1])

def solve(n):
    return 1-ans[bl(ans, -n)]
"""i = 0
j = 1
ans = []
m = -1
N = 10**3
while i<N:
    z = f(i)
    if m<z:
        m = z
        ans.append(i)
    i+=1
"""
dp = [0]
while dp[-1]<=10**18:
    dp.append((dp[-1]*k+k-1)//(k-1))
        
ans = [-i for i in dp][::-1]

for i in range(q):
    n = ni()-1
    print(solve(n))