MOD = 998
T = int(input())
for _ in range(T):
    N,M = map(int,input().split())
    K = [input().strip() for _ in range(M)]
    if N==0:
        for j in range(M):
            print(1)
    elif N==499:
        for j in range(M):
            a = int(K[j][-1])
            if a%2==0:
                print(1)
            else:
                print(500)
    elif N==1:
        for j in range(M):
            r = int(K[j][-1])
            n = 1
            for k in range(1,len(K[j])):
                n = (n*10)%MOD
                r = (int(K[j][-(k+1)])*n+r)%MOD
            print((r+1)%MOD)
    elif N%2==1:
        T = 498*998
        for j in range(M):
            r = int(K[j][-1])
            n = 1
            for k in range(1,len(K[j])):
                n = (n*10)%T
                r = (int(K[j][-(k+1)])*n+r)%T
            if K[j]!="0" and r==0:
                ans = 0
            else:
                ans = 1
                for k in range(1,r):
                    ans = (ans+pow(N,k,MOD))%MOD
            print(ans)
    else:
        x = N
        m = 0
        while x%2==0:
            m += 1
            x = x//2
        T = 498*166
        Tmax = T*998
        for j in range(M):
            rmax = int(K[j][-1])
            n = 1
            for k in range(1,len(K[j])):
                n = (n*10)%Tmax
                rmax = (int(K[j][-(k+1)])*n+rmax)%Tmax
            q = rmax//T
            r = rmax%T
            cnt = 0
            for k in range(1,T+1):
                cnt = (cnt+pow(N,k,MOD))%MOD
            ans = q*cnt+1
            for k in range(1,r+1):
                ans = (ans+pow(N,k,MOD))%MOD
            print(ans)