Lucy 的公司正在组织一场圣诞抽奖活动。共有 $N$ 名员工参加，活动期间，会有 $N$ 张纸条被放入帽子中，每位员工对应一张。第 $i$ 张纸条的面值为 $i$ 美元。随后，员工们将以随机顺序从帽子中抽取一张纸条。

或者说，他们本应如此。然而，Lucy 并不打算遵守规则，她计划在轮到自己时偷看帽子里的纸条，并拿走面值最高的那一张。

现在她想知道，假设她的所有同事都不作弊，她拿到的纸条的期望值是多少。不幸的是，她无法用通常的办公方式（即使用 Excel）解决这个问题，所以她向你寻求帮助。

输入格式

输入的第一行包含测试用例的数量 $Z$ ($1 \le Z \le 10^6$)。接下来是各测试用例的描述。

每个测试用例仅包含一行，即员工人数 $N$ ($1 \le N \le 10^6$)。

输出格式

可以证明，Lucy 拿到的纸条的期望值（以美元为单位）可以表示为一个不可约分数 $\frac{P}{Q}$，其中 $P, Q$ 为整数，且 $Q$ 与 $998244353$ 互质。

对于每个测试用例，请在单独的一行中输出 $P \cdot Q^{-1} \pmod{998244353}$ 的结果。

样例

输入格式 1

2
2
10

输出格式 1

249561090
390067951

说明

在第一个测试用例中，纸条的期望值为 $\frac{7}{4}$。