#include<bits/stdc++.h>
// #define endl '\n'
using namespace std;
using ll=long long;
const int N=1e7+9;
const int mod=998244353;
// const int mod=1e9+7;
const int inv2=(mod+1)>>1;
int T,n,c,fac[N],ifac[N],ffac[N],f[N],g[N];
inline int power(int a,int b){
	int s=1;
	for(;b;b>>=1,a=(ll)a*a%mod)
		if(b&1)s=(ll)s*a%mod;
	return s;
}
int main(){
#ifdef memset0
	freopen("G.in","r",stdin);
#endif
	ios::sync_with_stdio(0),cin.tie(0);
	fac[0]=ifac[0]=ifac[1]=ffac[0]=1;
	for(int i=2;i<N;i++)ifac[i]=(ll)(mod-mod/i)*ifac[mod%i]%mod;
	for(int i=1;i<N;i++){
		fac[i]=(ll)fac[i-1]*i%mod;
		ifac[i]=(ll)ifac[i-1]*ifac[i]%mod;
		ffac[i]=(ll)ffac[i-1]*((i<<1)-1)%mod;
	}
	f[0]=1;
	for(int i=1,x=(mod+1)>>1;i<N;i++){
		f[i]=(ll)x*ifac[i]%mod*ffac[i-1]%mod;
		x=x&1?(x+mod)>>1:x>>1;
		x=x?mod-x:x;
	}
	// for(int i=0;i<=10;i++)cerr<<f[i]<<" \n"[i==10];
	cin>>T;
	while(T--){
		cin>>n>>c;
		if(c==1){
			cout<<1<<endl;
			continue;
		}
		for(int i=0,cc=(ll)c*c%mod,x=1;i<=n;i++,x=(ll)x*cc%mod)g[i]=x;
		int ans=0;
		for(int i=0;i<=n;i++){
			int F=(ll)f[i]*(mod-c)%mod*power(4ll*(mod+1-c)%mod,i)%mod;
			if(i==0)F=((ll)F+c-2+mod)%mod;
			// fprintf(stderr,"i=%d f=%d g=%d\n",i,F,g[n-i]);
			ans=(ans+(ll)F*g[n-i])%mod;
		}
		cout<<(ll)ans*(mod-inv2)%mod<<endl;
	}
}
// 1 499122177 124780544 935854081 38993920 970948609 20471808 982159361 13069056 987353473
// 1 499122177 124780544 935854081 38993920 970948609 20471808 982159361 13069056 987353473