MOD = 998

def matrix(a, b):
    ans = [[0]*len(b[0]) for _ in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            ans[i][j] = sum(a[i][k]*b[k][j]%MOD for k in range(len(b)))%MOD
    return ans

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

    maxL = max(len(k) for k in K)
    dp = [N]
    dpN = []
    n = N
    for i in range(maxL-1):
        dp.append(dp[-1])
        dpN.append(n)
        for _ in range(9):
            dp[-1] = (dp[-1]*n%MOD+dp[-2])%MOD
        a = n
        for _ in range(9):
            n *= a
            n %= MOD
    dpN.append(n)
    
    for q in K:
        ans = 0
        for i, n in enumerate(q):
            n = int(n)
            idx = len(q)-1-i
            ans *= pow(dpN[idx], n, MOD)
            ans %= MOD
            SUM = 0
            for _ in range(n):
                SUM = (SUM*dpN[idx]%MOD+dp[idx])%MOD
            ans += SUM
            ans %= MOD
        ans += 1
        ans %= MOD
        print(ans)