题目描述

小于等于 $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$。