#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
int gcd(int a, int b)
{
return __gcd(a, b);
}
vector<int> get_factors(int m)
{
vector<int> factors;
for (int i = 1; i <= sqrt(m); ++i)
if (m % i == 0)
{
factors.push_back(i);
if (i != m / i)
factors.push_back(m / i);
}
return factors;
}
int solve(int n, int m)
{
vector<int> factors = get_factors(m);
int k = factors.size();
vector<int> factor_index(k);
for (int i = 0; i < k; ++i)
factor_index[i] = factors[i];
vector<vector<int>>
dp(n + 1, vector<int>(k, 0));
for (int j = 0; j < k; ++j)
dp[1][j] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j < k; ++j)
for (int l = 0; l < k; ++l)
if (gcd(factors[l], factors[j]) > 1)
dp[i][j] = (dp[i][j] + dp[i - 1][l]) % MOD;
int result = 0;
for (int j = 0; j < k; ++j)
result = (result + dp[n][j]) % MOD;
return result;
}
int main()
{
int n, m,
T;
cin >> m >> T;
while (T--)
{
cin >> n;
cout << solve(n, m) << endl;
}
return 0;
}