Background

给定整数n，需求：

其中，$\text{highbit}\left(i\right)$是指$i$的二进制的最高位1所在的位置，其中位置的顺序是自1开始，也即：$\text{highbit}\left(1\right)=1,\text{highbit}\left(2\right)=2$

Description

Format

Input

输入样例数T $1\leq T\le \sqrt{1919810\ 114514}$ 每行输入一个样例n $1\leq n\leq 10^{18}$

Output

每行输出n对应的计算结果，由于结果可能太大，因此对输出求模998244353

Samples

6
1
2
3
4
5
1569412564135

1
5
11
23
38
914293368

Limitation

1s, 1024KiB for each test case.