注意

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T679602

题目描述

计算：

$$\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$$

答案对 $\bm{998244353}$ 取模。

输入格式

第一行一个正整数 $T$ 表示数据组数。

下面 $T$ 行，每行两个非负整数 $n, k$。

输出格式

对于每组数据，输出一行一个非负整数表示答案。

样例

1
1 0

1

2
1 0
2 1

1
9

说明/提示

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^{12}$，$\bm{k \in \{0, 1\}}$。

Subtask	$q \le$	$n \le$	$k = 0$	分值	依赖子任务
1	$10^5$	$1$	不保证	5	-
2	$3$	$10$		20
3	$10^5$	$10^6$	保证	15
4		$10^{12}$			3
5		$10^6$	不保证		1 - 3
6		$10^{12}$		30	1 - 5