import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		int mod = 998;
		boolean[] b = new boolean[mod];
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < t; i++) {
			String[] sa = br.readLine().split(" ");
			int n = Integer.parseInt(sa[0]);
			int m = Integer.parseInt(sa[1]);
			Arrays.fill(b, false);
			List<Integer> list = new ArrayList<>();
			int v = 1;
			b[v] = true;
			list.add(v);
			int ls = 0;
			while (true) {
				v *= n;
				v %= mod;
				if (b[v]) {
					for (int j = 0; j < list.size(); j++) {
						if (list.get(j) == v) {
							ls = j;
							break;
						}
					}
					break;
				}
				b[v] = true;
				list.add(v);
				if (v == 0) {
					break;
				}
			}
			int size = list.size();
			int size1 = size - ls;
			int sum = 0;
			for (int j = ls; j < size; j++) {
				sum += list.get(j);
			}
			sum %= mod;

			for (int j = 0; j < m; j++) {
				long ans = 0;
				String s = br.readLine();
				if (b[0]) {
					if (s.length() > 5) {
						pw.println(sum);
					} else {
						int end = Integer.parseInt(s);
						if (end >= size) {
							pw.println(sum);
						} else {
							for (int k = 0; k <= end; k++) {
								ans += list.get(k);
							}
							ans %= mod;
							pw.println(ans);
						}
					}
				} else {
					long v2 = 0;
					for (int k = 0; k < s.length(); k++) {
						ans *= 10;
						ans %= mod;
						v2 *= 10;
						int c = s.charAt(k) - '0';
						v2 += c;
						if (v2 >= size) {
							v2 -= ls;
							ans += v2 / size1 * sum;
							ans %= mod;
							v2 %= size1;
							v2 += ls;
						}
					}
					for (int k = 0; k <= v2; k++) {
						ans += list.get(k);
					}
					ans %= mod;
					pw.println(ans);
				}
			}
		}
		pw.flush();
		br.close();
	}
}