Description

Positive integers less than or equal to $n$ form the set $S_n=\{1,2,\dots,n\}$.

The cost to delete the element with value $i$ is $i^k$, and each element can be deleted at most once.

Given positive integers $n$ and $k$, find: what is the minimum cost to make the product of all elements in $S_n$ a perfect square? Output the answer modulo $998244353$.

Note that you need to minimize the cost first, then take modulo $998244353$, rather than minimizing the cost after taking modulo $998244353$.

You need to answer $T$ queries, and all queries share the same $k$.

Input Format

The first line contains three positive integers $T$, $k$, and $\max n$, representing the number of queries, the given $k$, and the maximum $n$.

The next $T$ lines each contain one positive integer $n$.

Output Format

Output $T$ lines. On the $i$-th line, output the answer for the $i$-th query.

2 2 6
1
6

0
25

Hint

Explanation for Sample 1

For $n=1$, the product of $S_1$ is a perfect square, so no deletion is needed.

For $n=6$, you can delete $5$ to make the product of $S_6$ a perfect square.

Constraints

• 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): no additional constraints.

For $100\%$ of the testdata, $1\le \max n\le 5\times 10^6$, $1\le T\le 5\times 10^5$, $1\le k< 998244353$.

It is guaranteed that $1\le n\le \max n$.

Translated by ChatGPT 5