T = int(input())
MOD = 998
X = 498
for _ in range(T):
    N, M = map(int, input().split())
    N %= MOD
    p = [pow(N, i, MOD) for i in range(X)]
    S = sum(p) % MOD
    for __ in range(M):
        Ks = input()
        if N == 0:
            print(1)
            continue
        K = 0
        for c in Ks:
            K *= 10
            K += ord(c) - ord('0')
        K += 1
        A = K // X
        B = K % X
        ans = 0
        for i in range(B):
            ans += p[i]
        ans += (A % 998) * S
        print(ans % MOD)