def prime(n):
    n<2:return False
    if n==2:return True
    if n%2==0:return False
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:return False
    return True

k=int(input())
q=int(input())
l=[]
r=[]
for i in range(q):
    l.append(int(input()))
q=int(input())
for i in range(q):
    r.append(int(input()))

c=0
while c<q:
    ans=1
    for i in range(l[c],r[c]+1):
        if sum(list(map(int,str(i))))%k==0:
            if prime(i):
                ans*=i
    c+=1
    print(ans)