提交记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
//#define endl '\n'
const int N=200009;
const int INF=0x3f3f3f3f;
const int mod=998244353;
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48); ch=getchar();}
    return s*=f;
}
inline void write(int x){
    if(x>9)write(x/10);
    putchar(x%10+48);
}
inline void print(int x){
    if(x<0){putchar('-'); x=-x;}
    write(x);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> T rnd(T l,T r){return uniform_int_distribution<T>(l,r)(rng);}
inline void file(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
int n,m;
int p2[209],p[N][209],num[209][209];
//p[a][b]=a^b num[h][d]=2^(h+1)-1的满二叉树d路径数量
inline void init(){
	p2[0]=1; for(int b=1;b<=62;b++)p2[b]=p2[b-1]*2;
	for(int a=1;a<=100000;a++){
		p[a][0]=1;
		for(int b=1;b<=150;b++)p[a][b]=p[a][b-1]*a%mod;
	}
	num[0][0]=1;
	for(int h=1;h<=64;h++){
		for(int d=0;d<=h*2;d++){
			num[h][d]=num[h-1][d]*2%mod;
			for(int x=max(d-h,0ll),y;x<=h;x++){
				y=d-x;
				int px,py;
				if(x==0)px=1; else px=p[2][x-1];
				if(y==0)py=1; else py=p[2][y-1];
				num[h][d]=(num[h][d]+px*py%mod)%mod;
			}
		}
	}
}
int now[209];
inline int qpow(int a,int b){
	int ret=1;
	while(b){
		if(b&1)ret=ret*a%mod;
		a=a*a%mod; b>>=1;
	}
	return ret;
}
inline void solve(){
	n=read(); m=read();
	int h=log2(n+1)-1;
	memset(now,0,sizeof(now));
	for(int d=0;d<=h*2;d++)now[d]=num[h][d];
	int k=n-(p2[h+1]-1);
	for(int d=1;d<=h+1;d++)now[d]=(now[d]+k)%mod;
	for(int d=2;d<=h+1;d++){
		for(int t=1;t<d;t++)
			now[d+t]=(now[d+t]+(k%mod)*p[2][t-1])%mod;
	}
	now[0]=(now[0]+k)%mod;
	for(int d=1;d<=h+1;d++){
		int q=k/p2[d],r=k%p2[d]; q%=mod;
		now[d*2]=(now[d*2]+q*p[2][2*d-2]%mod)%mod;
		if(r>p2[d-1])now[d*2]=(now[d*2]+p[2][d-1]*((r-p[2][d-1])%mod+mod)%mod)%mod;
	}
	int ans=0;
	for(int d=0;d<=h*2+2;d++){
		if(d>=n)break;
		int tmp=p[m][d+2];
		for(int i=1;i<m;i++)tmp=((tmp-p[i][d+1])%mod+mod)%mod;
		int t=now[d]*qpow(m,n-d-1)%mod*tmp%mod;
		ans=(ans+t)%mod;
	}
	cout<<ans<<'\n';
}
signed main(){
	init();
    int _=read();
    while(_--){
    	solve();
	}
    return 0;
}