The condition on \(x\), “positive integers not exceeding \(N\),” is equivalent to “non-negative integers not exceeding \(N\).” We will find the answer under this substitution.

For a pair of non-negative integers \((i,j)\) with \(i\geq j\), let \(f(i,j)\) be the number of, and \(s(i,j)\) be the sum of, the non-negative integers strictly less than \(2^i\) with popcount \(j\). This can be computed with a DP (Dynamic Programming). Specifically, we can use the following relations: \(f(i,0)=f(i,i)=1\), \(s(i,0)=0\), \(s(i,i)=2^i-1\), and for \(0<j<i\), it holds that \(f(i,j)=f(i-1,j-1)+f(i-1,j)\) and \(s(i,j)=s(i-1,j)+s(i-1,j-1)+2^{i-1}\times f(i-1,j-1)\).
Mathematical analysis also shows that \(f(i,j)=\binom{i}{j}\), \(s(i,0)=0\), \(s(i,j)=\binom{i-1}{j-1}\times (2^i-1)\) (for \(j>0\)).

Let \(\mathrm{popcount}(N)=m\), and denote the integers \(i\) such that \(2^i\)s place of the binary representation of \(N\) is \(1\) as \(d_1,d_2,\ldots, d_m\) \((d_1>d_2\cdots>d_m)\). Obviously, \(N=\displaystyle\sum_{i=1}^m 2^{d_i}\).
Then, group the integers between \(0\) and \(N\) (inclusive) into the following \((m+1)\) groups, and find the sum of conforming integers in each group. For \(1\leq i\leq m\), the \(i\)-th group is formed by all integers between \(\displaystyle\sum_{j=1}^{i-1} 2^{d_j}\) (inclusive) and \(\displaystyle\sum_{j=1}^{i} 2^{d_j}\) (exclusive), and the \((m+1)\)-th group is formed solely by \(N\). For the \((m+1)\)-th group, the sum is \(N\) is \(m=K\) and \(0\) otherwise.

For an integer in the \(i\)-th group \((1\leq i\leq m)\), the standing bits beyond \(2^{d_i}\)s place are \(d_1, d_2,\ldots, d_{i-1}\), and the \(2^{d_i-1}\)s or lower places can take an arbitrary value, so the number of conforming integers is \(f(d_i,K-i+1)\), and their sum is \(S(d_i,K-i+1)+f(d_i,K-i+1)\times \displaystyle\sum_{j=1}^{i-1} 2^{d_j}\). Here, if \(K-i+1<0\) or \(d_i<K-i+1\), then there are zero integers, and the sum is zero too.

By precalculating \(f(i,j)\) and \(S(i,j)\), each group can be computed in \(O(1)\) time, so the problem can be solved in \(O(\log N)\) time per query. Since it is sufficient to precompute \(f(i,j)\) and \(s(i,j)\) for \(0\leq j\leq i\leq\lfloor \log_2 N\rfloor\), the precomputation costs \(O((\log N)^2)\) time. Therefore, the overall computational complexity is \(O((\log N+T)\log N)\), fast enough under the constraints of the problem. Thus, the problem has been solved.

Make sure to print the answer modulo \(998244353\).

Sample code in C++:

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

#define N 60

mint c[N+1][N+1]; //c[i][j]=(the number of x  s.t. 0<=x<(2^i), popcount(x)=j) for 0<=j<=i<=60
mint s[N+1][N+1]; //s[i][j]=(the sum    of x  s.t. 0<=x<(2^i), popcount(x)=j) for 0<=j<=i<=60

void preset(void){
	for(int i=0;i<=N;i++)for(int j=0;j<=N;j++){
		c[i][j]=0,s[i][j]=0;
	}
	c[0][0]=1;
	for(int i=0;i<60;i++){
		for(int j=0;j<=i;j++){
			c[i+1][j+1]+=c[i][j];
			s[i+1][j+1]+=s[i][j];
			s[i+1][j+1]+=(c[i][j]*((mint)2).pow(i));
			c[i+1][j]+=c[i][j];
			s[i+1][j]+=s[i][j];
		}
	}
	return;
}

int solve(long long n,int k){
	int a[N];
	for(int i=0;i<N;i++){
		a[i]=n&1;
		n=(n>>1);
	}
	int cur=0;
	mint offset=0;
	mint ans=0;
	for(int i=N-1;i>=0;i--){
		if(a[i]==1){
			if(cur<=k){
				ans+=s[i][k-cur];
				ans+=offset*c[i][k-cur];
			}
			cur++;
			offset+=((mint)2).pow(i);
		}
	}
	if(cur==k)ans+=offset;
	return (ans.val());
}

int main(void){
	preset();
	int t,k;
	long long n;
	cin>>t;
	for(int i=0;i<t;i++){
		cin>>n>>k;
		cout<<solve(n,k)<<endl;
	}
	return 0;
}