#include<bits/stdc++.h>
#define LL long long
using namespace std;
//_________________________________________________________________________________________________________________________________________
const int N = 100;
const LL MOD = 998244353; 
int k, T;
LL c[N][N], n;
void init0(){
	for(int i = 1; i <= 69; i++) c[i][0] = 1, c[i][i] = 1;
	for(int i = 1; i <= 69; i++){
		for(int j = 1; j < i; j++){
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
//			printf("%dC%d:%d\n", i, j, c[i][j]);
		}
	}
}

LL C(int n, int k){
	if(k > n || n < 0) return 0;
	if(n == 0 && k == 0) return 1;
	return c[n][k];
}

vector<int> vis;
LL calc(LL n, int k){
	LL ans = 0;
	vis.clear();
	for(int i = 62; i >= 0; i--){
		if(n & (1ll << i)){
			for(int j = 0; j < i; j++){
				ans = (ans + ((1 << j) % MOD) * C(i - 1, k - 1)) % MOD;
			}
			for(int j : vis){
				ans = (ans + ((1 << j) % MOD) * C(i, k)) % MOD;
			}
			vis.push_back(i);
			k--;
//			printf("%d %lld\n", i, ans);
		}
	}
	if(k == 0) ans = (ans + n) % MOD;
	return ans;
}

int main(){
	init0();
	scanf("%d", &T);
	while(T--){
		scanf("%lld%d", &n, &k);
		printf("%lld\n", calc(n, k));
	}
	return 0;
}