好题。
考虑计算 \(x\) 落在 \([1, n - 1]\) 的概率。设 \(f_i\) 为 \(x\) 经过 \(i\) 的概率，答案即为 \(\sum\limits_{i = 1}^{n - 1} f_i\)。
\(f\) 有一个朴素的递推：
\[f_i = \begin{cases} \frac{1}{2} (f_{i - 1} + f_{\frac{i}{2}}) & 2 \mid i \\ \frac{1}{2} f_{i - 1} & 2 \nmid i \end{cases} \]初值为 \(f_1 = 1\)。
发现每个状态的前驱数量很少，可以往矩阵优化上考虑。
但是当 \(i\) 为偶数的时候，我们需要知道 \(f_{\frac{i}{2}}\) 的值。当 \(\frac{i}{2}\) 为奇数时，\(f_i = \frac{1}{2} (f_{i - 1} + \frac{1}{2} f_{\frac{i}{2} - 1}) = \frac{1}{2} f_{i - 1} + \frac{1}{4} f_{\frac{i}{2} - 1}\)，否则继续展开：
\[\begin{aligned} f_i & = \frac{1}{2} f_{i - 1} + \frac{1}{2} f_{\frac{i}{2}} \\ & = \frac{1}{2} f_{i - 1} + \frac{1}{4} (f_{\frac{i}{2} - 1} + f_{\frac{i}{4}})\end{aligned} \]到这里还要继续讨论 \(\frac{i}{4}\) 的奇偶性，如果是偶数还要继续展开。于是可以发现，若设 \(\text{low}(i) = k\)（\(\text{low}(i)\) 为 \(i\) 的最低位从低到高从 \(0\) 开始的编号），那么：
\[f_i = \sum\limits_{j = 0}^k \frac{1}{2^{j + 1}} f_{\frac{i}{2^j} - 1} = \sum\limits_{j = 0}^k \frac{1}{2^{j + 1}} f_{\left\lfloor\frac{i - 1}{2^j}\right\rfloor} \]为了防止对边界的讨论，我们规定 \(f_0 = 2\)，因为 \(f_1 = \frac{1}{2} f_0 = 1\)。
于是，我们在答案向量中维护 \(\forall j \in [0, \log i], f_{\left\lfloor\frac{i}{2^j}\right\rfloor}\)。容易发现对于 \(\text{low}(i) = k\) 相同的 \(i\)，转移是相同的，都形如 \(\forall j \in [0, k], f_{\frac{i}{2^j}}\) 要从 \(\forall l \in [j, k], f_{\left\lfloor\frac{i - 1}{2^l}\right\rfloor}\) 转移过来。
于是我们设 \(\text{low}(i) = k\) 的所有 \(i\) 的转移矩阵为 \(F_k\)，\(i\) 的答案向量为 \(A_i\)，那么 \(A_i = A_{i - 1} F_{\text{low}(i)}\)，\(\forall j \in [0, \log n], A_{0, j} = 2\)。还要在转移的过程维护 \(\sum f\)，在 \(A_{i, 60}\) 处维护即可。
考虑像矩阵快速幂一样预处理。设 \(G_i = \prod\limits_{j = 1}^{2^i} F_{\text{low}(j)}, H_i = \prod\limits_{j = 1}^{2^{i + 1} - 1} F_{\text{low}(j)}\)。初始有 \(G_0 = H_0 = F_0\)。然后可以递推，\(G_i = H_{i - 1} F_i, H_i = G_i H_{i - 1}\)。
然后回答 \(n\) 时，维护一个答案向量 \(A\)，然后按 \(2\) 的次方分段计算即可。
时间复杂度 \(O((T + \log n) \log^3 n)\)。
code
// Problem: H. Asterism Stream
// Contest: Codeforces - Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/1864/H
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 63;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
struct mat {
ll a[maxn][maxn];
mat() {
mems(a, 0);
}
} f[maxn], g[maxn], h[maxn];
inline mat operator * (const mat &a, const mat &b) {
mat res;
for (int i = 0; i < maxn; ++i) {
for (int j = 0; j < maxn; ++j) {
for (int k = 0; k < maxn; ++k) {
res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
}
}
}
return res;
}
struct vec {
ll a[maxn];
vec() {
mems(a, 0);
}
};
inline vec operator * (const vec &a, const mat &b) {
vec res;
for (int i = 0; i < maxn; ++i) {
for (int j = 0; j < maxn; ++j) {
res.a[i] = (res.a[i] + a.a[j] * b.a[j][i]) % mod;
}
}
return res;
}
inline void init() {
for (int i = 0; i < 60; ++i) {
for (int j = 0; j <= 60; ++j) {
f[i].a[j][j] = 1;
}
f[i].a[0][60] = 1;
for (int j = 0; j <= i; ++j) {
ll coef = 1;
for (int k = j; k <= i; ++k) {
coef = coef * inv2 % mod;
f[i].a[k][j] = coef;
}
}
}
g[0] = h[0] = f[0];
for (int i = 1; i < 60; ++i) {
g[i] = h[i - 1] * f[i];
h[i] = g[i] * h[i - 1];
}
}
void solve() {
ll n;
scanf("%lld", &n);
vec ans;
for (int i = 0; i < 60; ++i) {
ans.a[i] = 2;
}
for (int i = 59; ~i; --i) {
if (n & (1LL << i)) {
ans = ans * g[i];
}
}
printf("%lld\n", (ans.a[60] + mod - 2) % mod);
}
int main() {
init();
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}