#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define int ll
#define pii pair<int,int>
#define mp make_pair
#define F(i,a,b) for(re int (i)=(a);(i)<=(b);(i)++)
#define DF(i,a,b) for(re int (i)=(a);(i)>=(b);(i)--)
#define G(i,u) for(re int (i)=head[u];(i);(i)=nxt[(i)])
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
const int N=1000010,p=998244353;
int n,k,tot;
il int fpow(int a,int b)
{
	int x=1;
	while(b)
	{
		if(b&1) x=x*a%p;
		a=a*a%p;
		b>>=1;
	}
	return x;
}
il int S(int x)
{
	x%=p;
	return x*(x+1)%p*(2*x+1)%p*fpow(6,p-2)%p;
}
il int get(int l,int r,int n)
{
	if(l>r) return 0;
	if(r>n/2&&l<=n/2) return (get(l,n/2,n)+get(n/2+1,r,n))%p;
	if(l>n/2) l=n-l,r=n-r,swap(l,r);
	return (n%p*((l+r)%p)%p*((r-l+1)%p)%p*fpow(2,p-2)%p-(S(r)-S(l-1)+p)%p+p)%p;
}
il void solve()
{
	n=read(),k=read();
	if(n<=28)
	{
		
	}
	else
	{
		int l=1,r=n,ans=0;
		DF(i,log2(n),0)
		{
			int cnt=(n>>i)+((n>>i)&1);
			int ls=cnt/2,rs=cnt-ls;
			if(l<n-r+1) swap(ls,rs);
			ans=(ans+(i+1)*get(l,l+ls-1,n+1)%p)%p;
			ans=(ans+(i+1)*get(r-rs+1,r,n+1)%p)%p;
			l+=ls,r-=rs;
		}
		printf("%lld\n",ans);
	}
}
signed main()
{
//	freopen("npc.in","r",stdin);
//	freopen("npc.out","w",stdout);
	int T=read();
	while(T--) solve();
	return 0;
}