MOD = 998

for _ in range(int(input())):
    N, M = map(int, input().split())
    K = [input() for _ in range(M)]

    S = set()
    B = []
    ans = 1
    SUM = 1
    while ans not in S:
        B.append(ans)
        S.add(ans)
        SUM *= N
        SUM %= MOD
        ans += SUM
        ans %= MOD
    L = len(B)

    for k in K:
        cnt = 0
        for n in k:
            cnt = (cnt*10+int(n))%L
        print(B[cnt])