给出两个结论

  1. 对 进行质因数分解，若只含有质因子和，则是不循环小数，即
  2. 否则，是循环的，且循环开始于小数点后第位，其中，表示表示质因数分解形式下的指数项，表示质因数分解下的指数项。即

首先，类似前缀和的思路，只要能求解~ 的答案，相减就可以得到的答案。下面，我们考虑一种类似容斥的做法，记表示~ 中的倍数有多少个。初始时，然后我们按照的值从大到小遍历，每遍历到一组，就对所有的进行一次。这样，当继续往下遍历的时候，就能保证总是能“恰好”被整除的数的个数（而不会被更大的数整除）。在遍历的时候顺便统计答案即可。

总复杂度，足够通过本题（尽管代入左式算出来会有的运算量，但由于上式复杂度估的很粗，偏大，实际上跑得很快）。

当然也可以使用二维树状数组继续优化，达到更优的复杂度。

结论二略证：首先，若无因子，由欧拉降幂，一定有解（由欧拉降幂），换言之，存在一个解和一个使得，因此我们可以通分：，则可以得出这是一个循环节长度为，循环节内容为的小数。例如，至于为什么一个数除以形如的数字会得到循环节为分子的无限循环小数，这个难以言传，但实际写一下竖式运算就会发现这个结论很对？总之，综上，若无因子，由上述推导，一定有循环且一定在小数点后1位开始，此时有。

而对于有因子的情况，我们乘以个10可以得到一个新的小数（这个小数分子可能不为1，但这没有影响，因为上一段的推导可以看出，分子只影响循环节的内容，不影响长度和开始位置），而此时，我们得到的小数是从小数点后第1位开始循环的，因此原数的。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T;
const ll inf=1e15,mod=998244353;
ll l,r,cnt[55][32],num[55][32];
ll solve(ll x){
    memset(cnt,0,sizeof(cnt));
    rep(i,0,50){
        rep(j,0,25){
            if(num[i][j])    cnt[i][j]=x/num[i][j];
        }
    }
    ll ret=0;
    per(k,0,75){
        rep(i,0,min(k,50)){
            int j=k-i;
            if(j>25)    continue;
            if(cnt[i][j]){
                ret+=((ll)(max(i,j)+1)*(cnt[i][j]-1));
                rep(ii,0,i){
                    rep(jj,0,j){
                        cnt[ii][jj]-=cnt[i][j];
                    }
                }
            }
        }
    }
    return ret;
}
int main(){
    rep(i,0,50){
        if(!i)    num[i][0]=1;
        else    num[i][0]=2ll*num[i-1][0];
        rep(j,1,25){
            num[i][j]=num[i][j-1]*5ll;
            if(num[i][j]>inf){
                break;
            }
        }
    }
    cin>>T;
    while(T--){
        scanf("%lld%lld",&l,&r);
        assert(l<=r&&l>0&&r>0&&r<=inf);
        printf("%lld\n",(solve(r)-solve(l-1))%mod);
    }
    return 0;
}