「MCOI-09」Greedy Deletion

小于等于 $n$ 的正整数形成集合 $S_n=\{1,2,\dots,n\}$。 删除值为 $i$ 的元素代价为 $i^k$，其中每一个元素至多被删一次。 给定正整数 $n$ 和 $k$，求：最小代价使 $S_n$ 乘积变为完全平方数是什么？答案对 $998244353$ 取模。 **注意你需要求最小代价，模 $998244353$，而不是模 $998244353$ 后的代价的最小值。** 你需要回答 $T$ 组询问，其中所有 $k$ 相同。

第一行三个正整数 $T$，$k$，$\max n$，分别表示询问数量，给定 $k$，以及最大 $n$。 接下来 $T$ 行，每行一个正整数 $n$。

输出 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案。

2 2 6
1
6

0
25

#### 样例 1 解释 对于 $n=1$，$S_1$ 乘积为完全平方数，不需要删除。 对于 $n=6$，可以删除 $5$ 使得 $S_6$ 乘积变为完全平方数。 #### 数据规模与约定 - Subtask 1（7 pts）：$\max n\le 20$。 - Subtask 2（37 pts）：$\max n\le 1000$。 - Subtask 3（11 pts）：$T\le 1000$。 - Subtask 4（45 pts）：无额外限制。 对于 $100\%$ 的数据，$1\le \max n\le 5\times 10^6$，$1\le T\le 5\times 10^5$，$1\le k< 998244353$。 **保证** $1\le n\le \max n$。