AT_pakencamp_2024_day1_q Large Heap 2

以下の問題の答えを $ 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 $ 個あります。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_{1} $ $ \mathrm{case}_{2} $ $ \vdots $ $ \mathrm{case}_{T} $ 各テストケースは以下の形式で与えられる。 > $ N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 例えば $ K=5 $ のとき、 $ P=\lbrace 1,2,3,5,4 \rbrace $ はヒープ的な順列です。 ### Constraints - $ 1 \leq T \leq 10^{6} $ - $ 1 \leq N \leq 10^{18} $ - 入力は全て整数