Background

“你问心无愧吗？”

机房的 W40 同学在分割圆的时候遇到了一个问题，你能帮帮他吗？

Description

给定一个圆，在圆上随机选 $k$ 条弦^[1]，求期望将圆分成多少份？

对 $998244353$ 取模^[2]。

$T$ 组询问。

Constraints and Subtasks

对于全部测试点，满足：

• $0\le k\le 10^{18}$。
• $1\le T\le 1000$。

另外，还有一些测试点满足特殊要求：

Input

输入内容从标准输入中给出，格式如下：

$ \boxed{\begin{aligned} & N_1 \\ & N_2 \\ & \cdots \\ & N_T \end{aligned}} $

Output

输出 $T$ 行，每行包含一个整数，表示问题的答案。

Samples

0

1

10

26

• 样例 $1$ 显然。
• 对于样例 $2$，我有一个绝妙的解释，可惜写不下。