//Fuyutsuki Saki Fan Club //2025/06/20 11:31 //LuoFeng Nanami ver. #include #define ll long long #define rll register ll #define F(i, a, b) for(rll i = a; i <= b; i++) #define Fdn(i, a, b) for(rll i = a; i >= b; i--) #define pii pair #define int ll #define fi first #define se second #define ld long double #define pid pair #define ull unsigned ll #define lb(x) lowbit(x) #define lwb lower_bound #define upb upper_bound #define pb push_back using namespace std; mt19937_64 rnd(time(0)); const int inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353; const ld eps = 1e-9; const int maxn = 2e5 + 7; int jc[maxn], inv[maxn], inj[maxn], pow2[maxn]; inline int C(int n, int m) { return ( n < m ? 0 : jc[n] * inj[m] % mod * inj[n - m] % mod ); } int q, B; struct query { int l, r, id; bool operator < (const query &x) const { return (l / B == x.l / B ? (r == x.r ? 0 : ((l / B) & 1) ^ (r < x.r)) : l < x.l); } } Q[maxn]; int ret = 1, L, R; int ans[maxn]; inline void LL() { (ret += C(L - 1, R)) %= mod; (ret *= inv[2]) %= mod; L--; } inline void RL() { (ret += ret + mod - C(L, R)) %= mod; L++; } inline void LR() { (ret += mod - C(L, R)) %= mod; R--; } inline void RR() { (ret += C(L, R + 1)) %= mod; R++; } signed main() { // freopen("saki.in", "r", stdin); // freopen("saki.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); jc[0] = jc[1] = inv[0] = inv[1] = inj[0] = inj[1] = 1, pow2[0] = 1, pow2[1] = 2; F(i, 2, maxn - 1) { jc[i] = jc[i - 1] * i % mod; inv[i] = (mod - mod / i) * inv[mod % i] % mod; inj[i] = inj[i - 1] * inv[i] % mod; pow2[i] = pow2[i - 1] * 2 % mod; } cin >> q; B = sqrt(q); F(i, 1, q) { cin >> Q[i].l >> Q[i].r; Q[i].l--, Q[i].r--; Q[i].id = i; } sort(Q + 1, Q + 1 + q); L = 0, R = 0; F(i, 1, q) { while(L > Q[i].l) LL(); while(R < Q[i].r) RR(); while(L < Q[i].l) RL(); while(R > Q[i].r) LR(); ans[Q[i].id] = ret * (pow2[Q[i].l + 1] + mod - 1) % mod; } F(i, 1, q) cout << ans[i] << '\n'; return 0; }