T=int(input())
mod=998
import sys
sys.set_int_max_str_digits(0)
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)
      CC=C[stop:]
      s=sum(CC)%mod
      ans+=(K//len(CC))*s+sum(CC[:K%len(CC)])%mod
      print(ans%mod)