询问有多少对序列(A,B)，满足：(|A|=m)，把所有(A_i+B_j)都丢进序列(C)中排序得到(0,1,2,dots,n-1)。
(Tle 500,m|nle 10^{12})
考虑暴力搜索的过程：
假设当前到达状态(A={0,1},B={0,2})。此时已经表示了(0dots 3)，于是要添加(4)进去。
注意到因为({0,1}*{0,2}={0,1,2,3})，有({0+4,1+4}*{0,2}={4,5,6,7})，于是在(A)后面丢(4,5)，变成({0,1,4,5})。
当然也可以丢多一些，比如变成({0,1,4,5,8,9,12,13})。这相当于将({0,1})分开很多份，第(k)份加上(4k)。
于是可以看成这样的过程：(A,B)轮流操作。假设当前的(A,B)能表示(0dots c-1)。每次选择一个不为(1)的数(d)，将当前序列复制(d)份（编号(0dots d-1)），第(k)份总体加上(kc)。
然后可以转化这样的问题：设(F(n,m)=sum_{1<d|n} F(m,frac{n}{d}))。(ans=F(m,frac{n}{m})+F(frac{n}{m},n))。
接下来就简单多了：考虑计算(F(n,m))。设(f_n(c))表示对(n)做除法(c)次变成(1)的方案数。显然这可以分解质因数，容斥，对每个质因数分别计算得到。(ans=sum f_n(c)(f_m(c-1)+2f_m(c)+f_m(c+1)))。
using namespace std;
#include <bits/stdc++.h>
#define N 1000005
#define ll long long
#define mo 998244353
ll qpow(ll x,ll y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
ll n,m;
int p[N],np;
bool inp[N];
void initp(int n=1000000){
for (int i=2;i<=n;++i){
if (!inp[i])
p[++np]=i;
for (int j=1;j<=np && i*p[j]<=n;++j){
inp[i*p[j]]=1;
if (i%p[j]==0)
break;
}
}
}
const int K=105;
ll fac[K],ifac[K];
void initC(int n=100){
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%mo;
ifac[n]=qpow(fac[n]);
for (int i=n-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
}
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
struct Query{
ll n;
ll d[K];
int e[K],k,s;
ll f[K];
void work(ll _n){
n=_n;
ll t=n;
k=0;
for (int i=1;i<=np && t!=1;++i)
if (t%p[i]==0){
d[++k]=p[i],e[k]=0;
while (t%p[i]==0)
t/=p[i],e[k]++;
}
if (t!=1)
d[++k]=t,e[k]=1;
s=0;
for (int i=1;i<=k;++i)
s+=e[i];
static ll g[N];
g[0]=(n==1);
for (int i=1;i<=s;++i){
g[i]=1;
for (int j=1;j<=k;++j)
g[i]=g[i]*C(e[j]+i-1,i-1)%mo;
}
for (int i=0;i<=s;++i){
f[i]=0;
for (int j=0;j<=i;++j)
(f[i]+=g[j]*C(i,j)*(i-j&1?-1:1))%=mo;
f[i]=(f[i]+mo)%mo;
}
}
ll askf(int x){
if (0<=x && x<=s)
return f[x];
return 0;
}
} qn,qm;
int main(){
freopen("wsm.in","r",stdin);
freopen("wsm.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
initp();
initC();
int T;
scanf("%d",&T);
while (T--){
scanf("%lld%lld",&n,&m);
n/=m;
if (n==1 || m==1){
printf("1
");
continue;
}
qn.work(n);
qm.work(m);
ll ans=0;
for (int i=0;i<=qn.s;++i)
(ans+=qn.askf(i)*(qm.askf(i-1)+qm.askf(i)*2+qm.askf(i+1)))%=mo;
printf("%lld
",ans);
}
return 0;
}