当 $k = 0$ 时，内部为 $1$ 当且仅当 $x = y$，答案为 $2^n - 1$。

当 $k = 1$ 时：

• $x = y$ 且 $\text{popcount}(x) = 1$ 时答案为 $2$，$x = y$ 且 $\text{popcount}(x) > 1$ 时答案为 $1$，这部分的答案为 $2^n + n - 1$。
• $\text{popcount}(x) > 1$ 时拿掉一个二进制位 $1$ 可以使得答案为 $1$，所有 $n$ 位二进制数中每位为 $1$ 的频率均为 $\dfrac{1}{2}$，一共 $2^{n - 1} \cdot n$ 个 $1$，去掉 $\text{popcount}(x) = 1$ 的情况后有 $2^{n - 1} \cdot n - n$ 个，考虑 $(x, y)$ 互换后这部分的答案为 $2^n \cdot n - 2n$ 个。
• 上面两部分求和得到 $(n + 1) \cdot (2^n - 1)$。

#include <bits/stdc++.h>
using namespace std;
long long p[32];
const int P = 998244353;
long long power(int x, long long y)
{
	y %= P - 1;
	long long ans = 1;
	for (int i = 29; i >= 0; i--)
		if (y & (1 << i)) ans = ans * p[i] % P;
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	p[0] = 2;
	for (int i = 1; i <= 30; i++)
		p[i] = p[i - 1] * p[i - 1] % P;
	int T;
	cin >> T;
	while (T--)
	{
		long long n, k;
		cin >> n >> k;
		if (k == 0) cout << power(2, n) - 1 << '\n';
		if (k == 1) cout << (n + 1) % P * (power(2, n) - 1) % P << '\n';
	}
	return 0;
}