存在一个整数 $x$ 满足 $1 \le x \le n$。你知道 $n$ 但不知道 $x$。

你可以进行如下猜测：随机选择一个整数 $y$，满足 $1 \le y \le n$（你的 $y$ 可以与之前的询问相同），你会被告知 $x < y$，$x > y$ 或 $x = y$。如果只剩下一个可能的 $x$ 满足所有条件，你将停止询问。

给定 $n$，如果 $x$ 是均匀随机选取的，那么你的期望询问次数是多少？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 对于每个测试用例，唯一的一行包含一个整数 $n$ ($1 \le n \le 10^9$)。

输出格式

对于每个测试用例，输出一个整数，表示期望询问次数对 $998244353$ 取模的结果。 形式上，可以证明所求的期望值可以表示为一个不可约分数 $p/q$，其中 $q \not\equiv 0 \pmod{998244353}$，且存在唯一的整数 $r$ 满足 $0 \le r < 998244353$ 且 $qr \equiv p \pmod{998244353}$。请输出这个 $r$。

样例

样例输入 1

2
1
2

样例输出 1

0
1