#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&-(x))
#define popcount(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define umap unordered_map
#define all(x) x.begin(),x.end()
#define mk make_pair
#define pb push_back
#define ckmax(x,y) x=max(x,y)
#define ckmin(x,y) x=min(x,y)
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define int long long
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
#define N 1048580
const int mo=998244353;
inline int qpow(int x,int b){
	int res=1;
	while(b){
		if(b&1) res=res*x%mo;
		x=x*x%mo,b>>=1;
	}
	return res;
}
inline void red(int &x){x>=mo?x-=mo:0;}
inline void clear(int *A,int x,int y){for(int i=x;i<y;++i) A[i]=0;}
inline void copy(int *A,int *B,int x,int y){for(int i=x;i<y;++i) A[i]=B[i];}
inline void mul(int *A,int *B,int x,int y){for(int i=x;i<y;++i) A[i]=A[i]*B[i]%mo;}
int cir[N],rt;
inline void NTT(int *f,int len,int tag){
	if(len!=rt) for(int i=0;i<len;++i) cir[i]=(cir[i>>1]>>1)|((i&1)?len>>1:0);
	rt=len;
	for(int i=0;i<len;++i) if(i<cir[i]) swap(f[i],f[cir[i]]);
	for(int l=2;l<=len;l<<=1){
		int sze=l>>1,buf=qpow(tag?3:332748118,(mo-1)/l);
		for(int i=0;i<len;i+=l){
			int bas=1;
			for(int j=i;j<i+sze;++j,bas=bas*buf%mo){
				int tmp=bas*f[j+sze]%mo;
				red(f[j+sze]=f[j]-tmp+mo),red(f[j]+=tmp);
			}
		}
	}
	if(tag==1) return;
	int invn=qpow(len,mo-2);
	for(int i=0;i<len;++i) f[i]=f[i]*invn%mo;
}
int tmul[N];
inline void polyMul(int *A,int *B,int len1,int len2){
	#define sav tmul
	int len=1;
	while(len<(len1<<1)) len<<=1;
	copy(sav,B,0,len);
	NTT(A,len,1),NTT(sav,len,1),mul(A,sav,0,len),NTT(A,len,0);
	clear(A,len2,len),clear(sav,0,len);
	#undef sav
}
int inv1[N],inv2[N],inv3[N];
inline void polyInv(int *A,int len){
	#define sav1 inv1
	#define sav2 inv2
	#define sav3 inv3
	int lim=1;while(lim<len) lim<<=1;
	sav1[0]=qpow(A[0],mo-2);
	for(int l=2;l<=lim;l<<=1){
		int r=l<<1;copy(sav3,A,0,l);
		for(int i=0;i<(l>>1);++i) sav2[i]=(sav1[i]<<1)%mo;
		NTT(sav1,r,1),mul(sav1,sav1,0,r);
		NTT(sav3,r,1),mul(sav1,sav3,0,r);
		NTT(sav1,r,0),clear(sav1,l,r);
		for(int i=0;i<l;++i) red(sav1[i]=sav2[i]-sav1[i]+mo);
	}
	copy(A,sav1,0,len);
	clear(sav1,0,lim<<1),clear(sav2,0,lim<<1),clear(sav3,0,lim<<1);
	#undef sav1
	#undef sav2
	#undef sav3
}
inline void polyDer(int *A,int len){
	for(int i=1;i<len;++i) A[i-1]=A[i]*i%mo;A[len-1]=0;
}
inline void polyInt(int *A,int len){
	for(int i=len-1;i>=1;--i) A[i]=A[i-1]*qpow(i,mo-2)%mo;A[0]=0;
}
int ln1[N];
inline void polyLn(int *A,int len){
	#define sav ln1
	copy(sav,A,0,len),polyDer(A,len),polyInv(sav,len);
	polyMul(A,sav,len,len),polyInt(A,len),clear(sav,0,len);
	#undef sav
}
int exp1[N],exp2[N];
inline void polyExp(int *A,int len){
	#define sav1 exp1
	#define sav2 exp2
	int lim=1;while(lim<len) lim<<=1;
	sav1[0]=1;
	for(int l=2;l<=lim;l<<=1){
		copy(sav2,sav1,0,l>>1),polyLn(sav2,l);
		for(int i=0;i<l;++i) red(sav2[i]=A[i]-sav2[i]+mo);
		red(sav2[0]=sav2[0]+1);
		polyMul(sav1,sav2,l,l);
	}
	copy(A,sav1,0,len),clear(sav1,0,lim),clear(sav2,0,lim);
	#undef sav1
	#undef sav2
}
int n=10,m,fac[N],ifac[N],f[N],g[N],h[N],F1[N],F2[N],F3[N],T[N],ans[N];
inline int C(int x,int y){
	if(y>x) return 0;
	return fac[x]*ifac[y]%mo*ifac[x-y]%mo;
}
signed main(){
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mo;
	ifac[n]=qpow(fac[n],mo-2);
	for(int i=n;i>=1;--i) ifac[i-1]=ifac[i]*i%mo;
	f[1]=1;
	for(int i=2;i<=n;++i){
		f[i]=qpow(i,i-2)*ifac[i]%mo;
	}
	copy(g,f,0,n+1);
	polyExp(g,n+1);
	for(int i=1;i<=n;++i){
		h[i]=f[i]*C(i,2)%mo;
	}
	polyMul(h,g,n+1,n+1);
	
	for(int i=1;i<=n;++i){
		F1[i]=i*f[i]%mo*fac[i]%mo*ifac[i-1]%mo;
	}
	polyMul(F1,F1,n+1,n+1);
	polyMul(F1,g,n+1,n+1);
	for(int i=2;i<=n;++i){
		F1[i]=F1[i]*fac[i-2]%mo;
	}
	
	for(int i=1;i<=n;++i){
		T[i]=i*f[i]%mo*fac[i]%mo*ifac[i-1]%mo;
	}
	copy(F2,T,0,n+1);
	polyMul(F2,T,n+1,n+1);
	for(int i=1;i<=n;++i){
		T[i]=f[i]*fac[i]%mo*ifac[i-1]%mo;
	}
	polyMul(F2,T,n+1,n+1);
	polyMul(F2,g,n+1,n+1);
	for(int i=3;i<=n;++i){
		F2[i]=F2[i]*fac[i-3]%mo;
	}
	
	for(int i=1;i<=n;++i){
		T[i]=i*f[i]%mo*fac[i]%mo*ifac[i-1]%mo;
	}
	copy(F3,T,0,n+1);
	polyMul(F3,T,n+1,n+1);
	T[1]=0;
	for(int i=2;i<=n;++i){
		T[i]=f[i]*fac[i]%mo*ifac[i-2]%mo;
	}
	polyMul(F3,T,n+1,n+1);
	for(int i=4;i<=n;++i){
		F3[i]=F3[i]*fac[i-4]%mo;
	}
	for(int i=1;i<=n;++i){
		ans[i]=(C(i,2)*F1[i]+C(i,3)*3*F2[i]*2+C(i,2)*C(i-2,2)*4%mo*F3[i]%mo)%mo;
	}
	for(int i=1;i<=n;++i){
		g[i]=g[i]*fac[i]%mo;
		h[i]=h[i]*fac[i]%mo;
	}
	for(int cas=read();cas--;){
		n=read(),m=read();
		int tmp=(g[n]*C(n,2)-h[n]+mo)%mo*m%mo*m%mo;
		red(tmp+=ans[n]);
		printf("%lld\n",tmp*qpow(g[n],mo-2)%mo);
	}
	return 0; 
}