你喜欢互动问题吗？

中文题目为机翻，原题目请参考英文题面

有一个整数 $x$ 满足 $1 \leq x \leq n$。你知道 $n$ 但不知道 $x$。

你可以做下面的猜测：随机选择一个统一满足 $1 \leq y \leq n$ 的整数 $y$（你的 $y$ 可能等于之前的查询），然后你会被告知是否 $x < y, x > y$ 或 $x = y$。如果只有一个可能的 $x$ 满足所有条件，您将停止查询。

给定 $n$，如果均匀随机地选择 $x$，您的预期查询次数是多少？

输入

第一行包含一个整数 $T \: (1 \leq T \leq 100)$ 表示测试用例的数量。

对于每个测试用例，唯一的一行包含一个整数 $n \: (1 \leq n \leq 10^9)$.

输出

对于每个测试用例，输出一个整数，表示预期查询次数对 $998244353$ 取模。

从形式上讲，可以证明所寻求的期望值可以表示为一个不可还原分数 $p/q$，它满足 $q \not\equiv 0 \bmod 998244353$，并且有一个唯一的整数 $r$ 满足 $0 \leq r < 998244353$ 和 $qr \equiv p \mod 998244353$。求这个 $r$。

示例

2
1
2

0
1