#include<bits/stdc++.h>
using namespace std;
int pw[8010][8010];
const int mod=998244353;
int qpow(int a,int b){
	int c=1;
	for(;b;b>>=1){
		if(b&1)c=1ll*a*c%mod;
		a=1ll*a*a%mod;
	}
	return c;
}
int jc[8010],ij[8010];
int C(int a,int b){
	if(a<b||a<0||b<0)return 0;
	return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;
}
int s[8010][8010];
int F(int a,int b){return 1ll*jc[a]*s[b][a]%mod;}
void sol(){
	int n,m;scanf("%d%d",&n,&m);
	int ans=F(m+1,n);
	(ans-=(((m+1)&1)?-1ll:1ll)*pw[m+1][n])%=mod;
	if(m&1)ans=mod-ans;
	printf("%d\n",(1ll*ans*qpow(pw[m][n],mod-2)%mod-1+mod)%mod);
}
const int N=8003;
void ad(int &x,int y){
	x+=y;if(x>=mod)x-=mod;
}
int f[8010][8010];
int main(){
	jc[0]=ij[0]=1;
	for(int i=1;i<=N;i++){
		jc[i]=1ll*i*jc[i-1]%mod,ij[i]=qpow(jc[i],mod-2);
		for(int j=1;j<=N;j++){
			if(j==1)pw[i][j]=i;
			else pw[i][j]=1ll*i*pw[i][j-1]%mod;
		}
	}
	s[0][0]=1;
	for(int i=1;i<=N;i++)for(int j=1;j<=i;j++){
		s[i][j]=(1ll*s[i-1][j]*j%mod+s[i-1][j-1])%mod;
	}
	int T;scanf("%d",&T);while(T--)sol();
	//sum i^n
	return 0;
}