#include<stdio.h>
int a[1003], sum[1003];
char s[100005];
void solve()
{
	int n, m;
	scanf("%d %d", &n, &m);
	int i, j;
	a[0] = 1;
	sum[0] = 0;
	sum[1] = 1;
	int left, right;
	for (i = 1, left = -1; left < 0; i++)
	{
		a[i] = a[i - 1] * n % 998;
		sum[i + 1] = (sum[i] + a[i]) % 998;
		for (j = 0; j < i; j++)
		{
			if (a[j] == a[i])
			{
				left = j;
				right = i;
				break;
			}
		}
	}
	int res;
	int len, k;
	for (; m > 0; m--)
	{
		scanf("%s", s);
		for (len = 0; s[len] != '\0'; len++);
		if (len < 5)
		{
			k = 0;
			for (i = 0; i < len; i++)
				k = 10 * k + s[i] - '0';
			k++;
			if (k <= left)
				res = sum[k];
			else
				res = sum[left];
			k -= left;
			if (k > 0)
			{
				res += k / (right - left) % 998 * (sum[right] - sum[left] + 998) % 998;
				k %= right - left;
				res += sum[left + k] - sum[left] + 998;
				res %= 998;
			}
			printf("%d\n", res);
		}
		else
		{
			res = sum[left];
			j = left - 1;
			if (j > 0)
			{
				for (i = len - 1; j > 0; i--)
				{
					k = j / 10;
					j %= 10;
					if (s[i] - '0' >= j)
						s[i] -= j;
					else
					{
						k++;
						s[i] = s[i] + 10 - j;
					}
					j = k;
				}
			}
			else if (j < 0)
			{
				for (i = len; i > 0; i--)
					s[i] = s[i - 1];
				s[0] = '0';
				s[len]++;
				for (i = len; s[i] > '9'; i--)
				{
					s[i - 1]++;
					s[i] -= 10;
				}
				len++;
			}
			k = 0;
			for (i = 0; i < len; i++)
				k = (10 * k + s[i] - '0') % (right - left);
			res += sum[left + k] - sum[left] + 998;
			j = k;
			for (i = len - 1; j > 0; i--)
			{
				k = j / 10;
				j %= 10;
				if (s[i] - '0' >= j)
					s[i] -= j;
				else
				{
					k++;
					s[i] = s[i] + 10 - j;
				}
				j = k;
			}
			k = 0;
			for (i = 0; i < len; i++)
				k = (10 * k + s[i] - '0') % 998;
			res += k * (sum[right] - sum[left] + 998) % 998;
			res %= 998;
			printf("%d\n", res);
		}
	}
	return;
}
int main()
{
	int t;
	scanf("%d", &t);
	for (; t > 0; t--)
		solve();
	return 0;
}