Problem Statement

A string $S$ satisfying the following conditions is called an "almost palindrome".

• $S$ is a string consisting of lowercase English letters from a to z.
• $S$ is not a palindrome.
• There exists an $i\ (1 \leq i \leq |S|)$ such that removing the $i$-th character from $S$ results in a palindrome.

For example, let $S = $ nyaan. $S$ is not a palindrome, but removing the 2nd character y gives naan, which is a palindrome, so $S$ is an "almost palindrome".

Given $N$, find the number of "almost palindromes" of length $N$, modulo $998244353$.

You are given $T$ test cases; find the answer for each of them.

Constraints

• All inputs are integers.
• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^6$

Input

$T$
$\mathrm{case}1$
$\vdots$
$\mathrm{case}T$

$N$

Output

Print $T$ lines, followed by a newline at the end.
On the $i$-th line, print the answer to the $i$-th test case.

Sample

5
1
2
3
100
133333

0
650
1300
81960607
708231776