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

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

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

constexpr int MOD = 998;
void madd(int& x, int y) {
	x = (x + y % MOD + MOD) % MOD;
}
// Bint
#include <boost/multiprecision/cpp_int.hpp>
using Bint = boost::multiprecision::cpp_int;
// using Bint = __int128_t;

void solve() {
	int n, m;
	cin >> n >> m;
	int l_st = -1, ln = -1, ad = -1;
	{
		map<int, pair<int, int>> mp;
		int sm = 1;
		int nw = 1;
		mp[nw] = {1, 0};
		rep(i, 1, 1000) {
			int nx = nw * n % MOD;
			sm = (sm + nx) % MOD;
			if (mp.count(nx)) {
				auto [bsm, j] = mp[nx];
				l_st = nx;
				ln = i - j;
				ad = (sm - bsm + MOD) % MOD;
				break;
			}
			mp[nx] = {sm, i};
			nw = nx;
		}
	}
	assert(ln != 0);
	rep(i, 0, m) {
		string s;
		cin >> s;
		if (n == 0) {
			cout << "1\n";
			continue;
		}
		Bint k(s);
		k++;
		int ans = 0;
		int nw = 1;
		while (k > 0) {
			if (nw == l_st && k > ln) {
				int tmp = (int)((k / ln) % MOD);
				madd(ans, tmp * ad);
				k %= ln;
				continue;
			}
			madd(ans, nw);
			nw = (nw * n) % MOD;
			k--;
		}
		cout << ans << '\n';
	}
}

int main() {
	int t = 1;
	cin >> t;
	while (t--) solve();

	// rep(n, 1, MOD) {
	// 	int l_st = -1, ln = -1, ad = -1;
	// 	{
	// 		map<int, pair<int, int>> mp;
	// 		int sm = 1;
	// 		int nw = 1;
	// 		mp[nw] = {1, 0};
	// 		rep(i, 1, 1000) {
	// 			int nx = nw * n % MOD;
	// 			sm = (sm + nx) % MOD;
	// 			if (mp.count(nx)) {
	// 				auto [bsm, j] = mp[nx];
	// 				l_st = nx;
	// 				ln = i - j;
	// 				ad = (sm - bsm + MOD) % MOD;
	// 				break;
	// 			}
	// 			mp[nx] = {sm, i};
	// 			nw = nx;
	// 		}
	// 	}
	// 	cout << n << " ; " << ln << '\n';
	// }
}