T=int(input())
mod=998

for _ in range(T):
  N,M=map(int, input().split())  
  D=[-1]*1000;C=[]
  now=1
  for i in range(1000):
    if D[now]==-1:
      D[now]=i
      C.append(now)
    else:
      stop=D[now]
      break 
    now=now*N%mod  
  mo=len(C);su=sum(C)%mod
  for _ in range(M):
    K=int(input())
    K+=1
    if K<=len(C):
      print(sum(C[:K])%mod)
    else:
      ans=su
      K-=len(C)
      C=C[stop:]
      su=sum(C)%mod
      ans+=(K//len(C))*su+sum(C[:K%len(C)])%mod
      print(ans%mod)