T679602 [CFCOI-R3-T1] 位运算(bit)

:::info[题目信息] - 出题人：[Hamburger999](https://www.luogu.com.cn/user/1045301) - 数据：[Hamburger999](https://www.luogu.com.cn/user/1045301) $\text{bit.cpp},1 \text{ s},512 \text{ MiB}$ :::

询问 $q$ 次，每次给定 $n,k$，求： $$ \sum_{x=1}^{2^n-1}\sum_{y=1}^{2^n-1} \Biggl \lfloor \frac{\operatorname{popcount}(x \operatorname{and} y)+k}{\operatorname{popcount}(x \operatorname{or} y)} \Biggr\rfloor $$ 答案对 $998244353$ 取模。 其中 $\operatorname{and},\operatorname{or},\operatorname{popcount}$ 运算分别为按位与，按位或，二进制下 $1$ 的个数。

第 $1$ 行，$1$ 个整数 $q$。 接下来 $q$ 行，每行 $2$ 个整数 $n,k$ 表示一组询问。

对于每组询问输出 $1$ 行，$1$ 个整数表示答案。答案对 $998244353$ 取模。

对于 $100\%$ 的数据，$1 \le q \le 10^5,1 \le n \le 10^{12},0 \le k \le 1$。 本题共 $20$ 个测试点，每个测试点 $5$ 分，数据范围如下： ::cute-table{tuack} | 测试点编号 | $q \le$ | $n \le$ | $k \le$ | |:-:|:-:|:-:|:-:| | $1$ | $10^5$ | $1$ | $1$ | | $2 \sim 5$ | $3$ | $10$ | ^ | | $6 \sim 8$ | $10^5$ | $10^6$ | $0$ | | $9 \sim 11$ | ^ | $10^{12}$ | ^ | | $12 \sim 14$ | ^ | $10^6$ | $1$ | | $15 \sim 20$ | ^ | $10^{12}$ | ^ |