問題文

以下の問題の答えを f(K) とします。

(1,2,\ldots,K) の順列 P=(P_{1},P_{2}, \ldots ,P_{K}) を考えます。 P が以下の条件をすべて満たすとき、それを ヒープ的な 順列と呼ぶことにします。

• 2P_{i} \leq P_{2i} \left(1 \leq i \leq \left\lfloor \frac{K}{2} \right\rfloor \right)

• 2P_{i} \leq P_{2i+1} \left(1 \leq i \leq \left\lfloor \frac{K-1}{2} \right\rfloor \right)

ヒープ的な順列の個数を求めてください。

N が与えられるので、 f(1)+f(2)+ \cdots +f(N) を 998244353 で割った余りを求めてください。

1 つの入力につきテストケースは T 個あります。

制約

• 1 \leq T \leq 10^{6}
• 1 \leq N \leq 10^{18}
• 入力は全て整数

入力例 1

3
6
1
1000

出力例 1

9
1
465040340

例えば K=5 のとき、 P=\lbrace 1,2,3,5,4 \rbrace はヒープ的な順列です。