你是某人工智能公司的老板，该公司开发与数学相关的聊天机器人。通常情况下一切运行正常，但今天情况并非如此。所有与人工智能相关的机器刚刚崩溃，更糟糕的是，今天是著名的年度国际荒谬计算竞赛（ICPC）举办的日子……

在 ICPC 期间，参赛者们倾向于使用你公司的服务来求出某些算术表达式的精确值。今年也不例外：在比赛期间，你已经收到了大量的查询，但不幸的是，你无法回答它们。

在提交的每个查询中，你被要求计算一个算术表达式的精确值——一个长度恰好为 $n$ 的字符串，其中 $n$ 是一个奇数，满足以下条件：

• 该字符串仅由 $0$ 到 $9$ 的数字和算术运算符 ‘+’、‘-’、‘*’、‘/’ 组成；
• 处于奇数（第 $1, 3, \dots, n$ 个）位置的字符是数字，其余位置的字符是算术运算符；
• 表达式中 ‘/’ 符号后绝不会紧跟数字 $0$。

例如，表达式 ‘1*2/3+4-5’、‘0’ 和 ‘9/2’ 在某些 $n$ 的取值下满足上述条件，而 ‘23-5’、‘-7’、‘5/0’ 和 ‘998244353’ 则不满足。

在计算表达式的值时，当然需要遵循通常的算术运算优先级规则：首先，从左到右执行所有的乘法和除法，然后从左到右执行所有的加法和减法。

当员工们正在修复故障时，你产生了一个疑问：假设满足上述条件的每个算术表达式在下一次查询中出现的概率相等，那么该查询中表达式结果的期望值是多少？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2 \cdot 10^4$)，表示测试用例的数量。

接下来的 $T$ 行中，每行包含一个奇数 $n$ ($1 \le n < 10^{18}$)，表示算术表达式的长度。

输出格式

对于每个测试用例，输出一个整数 $R$ ($0 \le R < 998\,244\,353$)，使得如果期望值等于不可约分数 $\frac{P}{Q}$，则 $P \equiv QR \pmod{998\,244\,353}$。

可以证明，对于任何 $n$，期望值都是一个有理数，且这样的 $R$ 总是存在的。

样例

样例输入 1

7
1
3
5
7
9
998244353
111111111224317155

样例输出 1

499122181
137441435
101569571
823750769
719161256
368379914
253718992

说明

前三个测试用例的答案分别为 $\frac{9}{2}$、$\frac{170\,929}{21\,840}$ 和 $\frac{25\,555\,213\,441}{2\,146\,435\,200}$。