#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define mod 998244353LL
using namespace std;

struct Matrix{
	int r, c;
	long long data[33][33];
	
	Matrix operator * (const Matrix &a) const{
		Matrix res;
		res.r = r, res.c = a.c;
		for (int i = 1; i <= res.r; i ++){
			for (int j = 1; j <= res.c; j ++){
				res.data[i][j] = 0;
			}
		}
		for (int i = 1; i <= res.r; i ++){
			for (int j = 1; j <= res.c; j ++){
				for (int k = 1; k <= c; k ++){
					res.data[i][j] += data[i][k] * a.data[k][j];
					res.data[i][j] %= mod;
				}
			}
		}
		return res;
	}
};

int Q;
long long M, N;
vector<int> fac;

Matrix qpow(Matrix a, long long b){
	Matrix res;
	res.r = res.c = a.r;
	for (int i = 1; i <= res.r; i ++){
		for (int j = 1; j <= res.c; j ++){
			if (i == j) res.data[i][j] = 1;
			else res.data[i][j] = 0;
		}
	}
	while (b){
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

void __init(){
	fac.push_back(-1);
	for (int i = 1; i <= M / i; i ++){
		if (M % i) continue;
		fac.push_back(i);
		if (M / i != i) fac.push_back(M / i);
	}
	sort(fac.begin(), fac.end());
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("../data.in", "r", stdin);
	freopen("../data.out", "w", stdout);
#endif

	scanf("%lld %d", &M, &Q);
	__init();
	Matrix cur;
	cur.r = cur.c = fac.size() - 1;
	for (int i = 1; i < fac.size(); i ++){
		for (int j = 1; j < fac.size(); j ++){
			if (__gcd(fac[i], fac[j]) == 1) cur.data[i][j] = 0;
			else cur.data[i][j] = 1;
		}
	}
	while (Q --){
		scanf("%lld", &N);
		Matrix ans;
		ans.r = 1, ans.c = fac.size() - 1;
		for (int i = 1; i < fac.size(); i ++) ans.data[1][i] = 1;
		ans = ans * qpow(cur, N - 1);
		long long cnt = 0;
		for (int i = 1; i < fac.size(); i ++){
			cnt = (cnt + ans.data[1][i]) % mod;
		}
		printf("%lld\n", cnt % mod);
	}

	return 0;
}