ICPC chennia 2023 B

#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;
const unsigned long long B = 1ll<<62;
const int K = 1e6;
const int mod = 998244353;
struct num{
    vector<unsigned long long> n;
    num():n(1){}
    void reduce(){
        bool c = 0;
        for(int i=0;i<n.size();++i){
            n[i]+=c;
            if(n[i]>=B){
                n[i]-=B;
                c = 1;
            }
            else{
                c = 0;
            }
        }
        if(c){
            n.push_back(1);
        }
    }
    num(vector<unsigned long long> a){n=a;reduce();}
    num& operator ++(){
        n[0]++;
        reduce();
        return *this;
    }
    num operator +(const num &other)const{
        vector<unsigned long long> temp = other.n;
        temp.resize(max(temp.size(),n.size()));
        for(int i=0;i<n.size();++i)
            temp[i]+=n[i];
        return num(temp);
    }
    bool operator < (const num& other)const{
        if(n.size()!=other.n.size())return n.size()<other.n.size();
        for(int i=n.size()-1;i>=0;--i){
            if(n[i]!=other.n[i])return n[i]<other.n[i];
        }
        return false;
    }
    bool operator == (const num& other)const{
        if(n.size()!=other.n.size())return false;
        for(int i=n.size()-1;i>=0;--i){
            if(n[i]!=other.n[i])return false;
        }
        return true;
    }
    void print(){
        for(int i=n.size()-1;i>=0;--i){
            cout<<n[i];
        }
        cout<<"\n";
    }
};
struct node{
    int base,digit;
    num cur,add;
    int gcur,gadd;
    node(int _base):
        base(_base),
        digit(1),
        cur(vector<unsigned long long>(1,1)),
        add(vector<unsigned long long>(1,1)),
        gcur(1),
        gadd(1){}
    bool operator < (const node&other)const{
        return other.cur<cur;
    }
    node & operator ++ (){
        ++digit;
        cur = cur+add;
        gcur+=gadd;
        if(gcur>=mod){
            gcur-=mod;
        }
        if(digit==base){
            digit = 1;
            ++cur;
            add = cur;
            ++gcur;
            if(gcur==mod)gcur=0;
            gadd = gcur;
        }
        return *this;
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    num cur;
    priority_queue<node> q;
    for(int i=2;i<=16;++i){
        q.push(node(i));
    }
    vector<int> pre(1);
    for(int i=0;i<K;++i){
        auto t = q.top();
        q.pop();
        if(cur==t.cur){
            --i;
        }
        else{
            cur = t.cur;
            int x = pre.back()+t.gcur;
            if(x>=mod)x-=mod;
            pre.push_back(x);
        }
        ++t;
        q.push(t);
    }
    int t;
    cin>>t;
    while(t--){
        int k1,k2;
        cin>>k1>>k2;
        cout<<((pre[k2]-pre[k1-1]+mod)%mod)<<"\n";
    }
}