#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = (ll)s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

#define TT template <typename T>
template <class T1, class T2>
bool chmin(T1& x, T2 y) { return x > y ? (x = y, true) : false; }
template <class T1, class T2>
bool chmax(T1& x, T2 y) { return x < y ? (x = y, true) : false; }

struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
        srand(time(NULL));
    }
} io_setup;

const int MOD = 998;

void solve() {
    int N, M;
    cin >> N >> M;
    vector V(MOD, vector<int>(MOD, -1));
    vector<int> val;
    int a = 1, b = 0, c = 1;
    val.push_back(c);
    while (V[a][c] == -1) {
        V[a][c] = b;
        a = a * N % MOD;
        b++;
        c = (a + c) % MOD;
        val.push_back(c);
    }
    vector<int> A(MOD * MOD), C(MOD * MOD);
    A[0] = a, C[0] = c;
    rep(i, 1, MOD * MOD) {
        A[i] = A[i - 1] * N % MOD;
        C[i] = (A[i] + C[i - 1]) % MOD;
    }
    while (M--) {
        string K;
        cin >> K;
        int l = (int)K.size();
        if (l < 9 && stoi(K) <= b) {
            cout << val[stoi(K)] << "\n";
        } else {
            int amari = 0, now = 1;
            rep(i, 0, l) {
                amari += now * (K[l - 1 - i] - '0');
                amari %= b - V[a][c];
                now = (10 * now) % (b - V[a][c]);
            }
            amari -= b % (b - V[a][c]);
            if (amari < 0) amari += (b - V[a][c]);
            cout << C[amari] << "\n";
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

/*
import sys
sys.set_int_max_str_digits(0)

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