MOD = 998
T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    for _ in range(M):
        K = int(input())
        li = [[-1 for _ in range(MOD)] for _ in range(MOD)]
        a = 1
        b = 0
        c = 1
        while K > 0 and li[a][c] == -1:
            K -= 1
            li[a][c] = b
            a = a * N % MOD
            b += 1
            c = (c + a) % MOD
        if K == 0:
            print(c)
        else:
            K %= b - li[a][c]
            while K > 0:
                K -= 1
                a = a * N % MOD
                c = (c + a) % MOD
            print(c)