#include <cstdio>

using namespace std;
typedef long long ll;

const int mod = 998244353;
int pr[105], pw[105];
int pww[105][105];
int f2[4][8], c;
int f(int p, int z, int k)
{
	int tmp, ans, q = 2 * (((pr[p] + 1) / 2) & 1) - 1;
	if(pr[p] == 2)
	{
		tmp = ((k > 3) ? pww[p][k - 3] : 1);
		k = ((k > 3) ? 3 : k);
		ans = (ll)tmp * f2[k][z & ((1 << k) - 1)] % mod;
	}
	else
		ans = (ll)pww[p][k - 1] * ((z % pr[p]) ? (pr[p] - q) : ((pr[p] - 1) * (q + 1))) % mod;
	return ans;
}
int g(int p, int z, int k)
{
	if(!k)
		return 1;
	int res = 0;
	if(k > 1 && !(z % pww[p][2]))
		res = (ll)pww[p][2] * g(p, z / pww[p][2], k - 2) % mod;
	if(k == 1 && !(z % pr[p]))
		res = 1;
	return (res + f(p, z, k)) % mod;
}
void work(int m)
{
	int i;
	c = 0;
	for(i = 2; (ll)i * i <= m; i++)
		if(!(m % i))
		{
			pr[++c] = i;
			pww[c][pw[c] = 0] = 1;
			while(!(m % i))
			{
				pww[c][pw[c] + 1] = pww[c][pw[c]] * i;
				++pw[c];
				m /= i;
			}
		}
	if(m > 1)
	{
		pr[++c] = m;
		pw[c] = 1;
		pww[c][0] = 1;
		pww[c][1] = m;
	}
}

int main()
{
	int n, m, i, j, k, z, ans;
	for(i = 1; i <= 3; i++)
		for(j = 0; j < (1 << i); j++)
			for(k = 0; k < (1 << i); k++)
				if((j | k) & ((1 << (i - 1)) - 1))
				f2[i][(j * j + k * k) & ((1 << i) - 1)]++;
	scanf("%d%d", &m, &n);
	work(m);
	while(n--)
	{
		scanf("%d", &z);
		ans = 1;
		for(i = 1; i <= c; i++)
			ans = (ll)ans * g(i, z, pw[i]) % mod;
		printf("%d\n", ans);
	}
	return 0;
}