Description

设 $S$ 是一个长度为 $n$ 的字符串，由小写英文字母组成。

你的任务是统计：在所有长度为 $n$ 的字符串 $S$ 中，使得 不同的子回文串 数量最少的字符串有多少个。

子回文串 是指一个回文子串。

两个子回文串 $u$ 和 $v$ 是不同的，当且仅当它们的长度不同，或者存在某个位置 $i$（$0 \le i < \text{length}$）使得 $u_i \ne v_i$。

例如，字符串 "aaaa" 只包含 4 个不同的子回文串，分别是 "a"、"aa"、"aaa" 和 "aaaa"。

Format

Input

第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试用例的数量。

每个测试用例只有一行，包含一个整数 $n$（$1 \le n \le 10^9$）。

Output

对于每个测试用例，输出一行，包含一个整数，表示满足条件（即具有最少的不同子回文串数量）的字符串个数。

由于答案可能很大，请对 $998244353$ 取模。

Samples

2
1
2

26
676