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

int Q;
long long M, N;
long long dp[1003][1003];
vector<int> fac;

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();
	for (int i = 1; i < fac.size(); i ++) dp[1][i] = 1;
	for (int i = 1; i <= 1000; i ++){
		for (int j = 1; j < fac.size(); j ++){
			// printf("%-9d ", dp[i][j]);
			for (int k = 1; k < fac.size(); k ++){
				if (__gcd(fac[j], fac[k]) == 1) continue;
				dp[i + 1][k] += dp[i][j];
				dp[i + 1][k] %= mod;
			}
		}
		// cout << "\n";
	}
	while (Q --){
		scanf("%lld", &N);
		long long ans = 0;
		for (int i = 1; i < fac.size(); i ++){
			ans = (ans + dp[N][i]) % mod;
		}
		printf("%lld\n", ans % mod);
	}

	return 0;
}